[백준 node.js] 1012번_유기농 배추

백준 DFS 알고리즘 1012번_유기농 배추

난이도 : 실버II

 

문제 설명

입출력

 

문제 풀이 : 이 문제는 백준 11724번 연결 요소의 개수 문제와 유사하다.  참고할것(ghost4551.tistory.com/26)

연결 요소 찾기와 유사하게 로직을 작성하되 몇가지만 고려해주면된다.

1. 배추가 위치한 곳은 1이된다. 한번 방문했다면 해당노드를 0의 값으로 만들어준다. (방문처리)

2. 상하좌우 옮겨갈수 있으므로 옮겨주되 그래프의 범위인지 검사

크게 이렇게 두가지만 고려해주면 된다.

 

function solution() {
  let cnt = 0;
  //그래프 전체 탐색
  for (let i = 0; i < m; i++) {
    for (let j = 0; j < n; j++) {
      //그래프의 값을 돌면서 1이 존재하고 방문한적 없다면
      //해당 위치의 범위에는 DFS가 실행되지 않았으므로 실행
      if (graph[i][j] === 1) {
        DFS(i, j);
        //DFS가 한번 수행되고 나면 해당 노드의 인접노드까지 방문처리가 된다.
        //즉 하나의 배추집단을 파악한 셈이다.
        cnt += 1;
      }
    }
  }
  console.log(cnt);
}

function DFS(i, j) {
  //현재 i,j값이 그래프 범위내인지 검사
  if (RangeCheck(i, j) === true) {
    //현재 위치가 1이고(배추 존재)하고 방문한적없다면
    //방문 처리후 순서대로 DFS
    if (graph[i][j] === 1) {
      graph[i][j] = 0;
      DFS(i + 1, j); //아래
      DFS(i, j + 1); //오른쪽
      DFS(i - 1, j); //위
      DFS(i, j - 1); //왼쪽
    }
  } else {
    return;
  }
}

//그래프(배열) 범위 검증
function RangeCheck(i, j) {
  if (i >= 0 && i < m && j >= 0 && j < n) {
    return true;
  } else return false;
}

const readline = require("readline");
const rl = readline.createInterface({
  input: process.stdin,
  output: process.stdout,
});

let input = [];
let [m, n, k] = [0];
let graph = [];
rl.on("line", function (line) {
  //여러줄 입력
  input.push(line);
}).on("close", function () {
  let t = parseInt(input[0]);
  input = input.slice(1);
  //테스트 케이스 개수만큼 반복
  for (let i = 0; i < t; i++) {
    [m, n, k] = input[0].split(" ").map((el) => parseInt(el));
    //가로 세로 길이에 맞게 그래프와 방문자 수 초기화
    graph = Array.from(Array(m), () => Array(n).fill(0));
    //일반적인 DFS와 다르게 정점과 간선으로 이루어진 그래프가 아니라 배추의 위치가 주어지기 때문에
    //input배열 0에는 n,m,k값이 있으므로 1부터 수행
    for (let j = 1; j <= k; j++) {
      //배추 위치
      let [x, y] = input[j].split(" ").map((el) => parseInt(el));
      graph[x][y] = 1;
    }
    solution();
    //하나의 테스트 케이스가 끝난후 배열을 잘라 다음 테스트케이스 수행
    input = input.slice(k + 1);
    //배열 초기화
    graph.length = 0;
  }

  process.exit();
});

 

* 원래는 방문처리를 위해 graph의 크기와 똑같이 visited(방문처리)도 이중배열로 만들어서 일반적인 DFS처럼 

실행전에 visited 방문처리가 안되어있으면 DFS실행하고 방문처리해주었다.

문제를 풀고나서 다른 사람들 코드를 훑어보았는데 방문처리대신 그냥 배추의 위치를 0으로 바꿔주면 훨씬 깔끔하게 처리가 되었다. 이래서 다른 사람들 코드를 보는것도 중요한것 같다.