[백준] 1012. 유기농 배추

https://www.acmicpc.net/problem/1012

최종 제출

let fs = require('fs');
let input = fs.readFileSync('/dev/stdin').toString().trim().split('\n');

const testCaseSize = +input[0];
let testStartIndex = 1;

const dx = [-1, 1, 0, 0];
const dy = [0, 0, -1, 1];

let answer = "";

for (let i = 0; i < testCaseSize; i++) {
  const [width, height, cabbageAmount] = input[testStartIndex].split(" ").map(Number);
  const cabbage = input.slice(testStartIndex + 1, testStartIndex + cabbageAmount + 1);
  const field = [];

  // 밭 만들기
  for (let i = 0; i < width; i++) {
    let array = new Array(height).fill(0);
    field.push(array)
  }

  // 배추 심기
  cabbage.forEach(str => {
    let [x, y] = str.split(" ");
    field[+x][+y] = 1;
  });

  const bfs = (field, node) => {
    const queue = [node];

    // 인접 노드를 다 돌때까지 반복
    while (queue.length > 0) {
      let [x, y] = queue.shift();

      if (field[x][y] === 0) continue; // 배추가 없는 곳은 그냥 지나친다

      field[x][y] = 0; // 배추가 있다고 체크한 곳은 0으로 변환!

      // 상하좌우에 인접노드가 있나 검색
      for (let i = 0; i < 4; i++) {
        const nx = x + dx[i];
        const ny = y + dy[i];
        if (nx < width && nx >= 0 && ny < height && ny >= 0) {
          if (field[nx][ny] === 1) {
            // 돌아볼 인접 노드 목록에 추가
            queue.push([nx, ny])
          }
        }
      }
    }
  }

  let count = 0;
  for (let i = 0; i < width; i++) {
    for (let j = 0; j < height; j++) {
      if (field[i][j] === 1) {
        bfs(field, [i, j]);
        count++;
      }
    }
  }

  testStartIndex = testStartIndex + cabbageAmount + 1;
  answer += count + "\n";
}
console.log(answer)

BFS 알고리즘을 공부 후 처음 풀어 본 알고리즘이다.

DFS 알고리즘을 공부하고 DFS 알고리즘 문제도 풀어본 터라 조금은 그래프 탐색에 익숙해 져서 BFS도 호기롭게 도전했다.
그러나 로컬에서는 잘 동작했지만...

역시나 바로 되지 않았고, 시간 초과의 늪에 빠졌다... 원인은 역시 나의 바보 같음이었다.

BFS에서는 DFS와 달리 방문한 노드를 따로 저장하고, 검사할 필요가 없다. 그냥 지나쳐온 노드의 값을 변경 해주면 더 쉽게 해결할 수 있었다.

아직은 둘이 조금 헷갈리기에 BFS와 DFS의 풀이 방법 차이를 명확히 공부해야겠다.