출처

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

문제풀이

const input = require("fs").readFileSync("/dev/stdin").toString().trim().split("\n");
const num = Number(input.shift());
const ds = [
  [-1, 0],
  [1, 0],
  [0, 1],
  [0, -1],
];
function bfs(startX, startY) {
  //시작 좌표 기준으로 시작
  const queue = [[startX, startY]];
  // queue가 비워지면 탈출
  while (queue.length) {
    const [x, y] = queue.shift();
    // queue의 값을 하나씩 빼서 xy로 저장
    // xy좌표가 0 이면 다시, 1이면 0으로 만들어준다.
    // 인접한 1들 다 0으로 만들기
    if (!map[x][y]) continue;
    else map[x][y] = 0;

    // 상하좌우 탐색하여 1이 있다면 queue에 push 해준다.
    for (let i = 0; i < 4; i++) {
      const xPos = x + ds[i][0];
      const yPos = y + ds[i][1];

      if (xPos < 0 || yPos < 0 || xPos >= M || yPos >= N) continue;
      if (map[xPos][yPos]) queue.push([xPos, yPos]);
    }
  }
}
for (let i = 0; i < num; i++) {
  let worm = 0;
  var [M, N, K] = input.shift().split(" ").map(Number);
  var map = Array.from(Array(M), () => new Array(N).fill(0));
  for (let j = 0; j < K; j++) {
    let xy = input.shift().split(" ");
    map[xy[0]][xy[1]] = 1;
  }
  for (let k = 0; k < M; k++) {
    for (let l = 0; l < N; l++) {
      //만약 그 좌표가 1이라면 worm을 늘려주고 상하좌우 탐색하여 전부 0으로 만들어준다.
      if (map[k][l]) {
        bfs(k, l);
        worm++;
      }
    }
  }
  console.log(worm);
}

내가 제일 못하는 그래프 탐색 문제였다. 그리고 처음 접하는 BFS를 사용하는 문제..
처음에는 조건문 지옥으로 정답은 나오게 구현하였으나, 백준 채점 결과 틀렸습니다가 계속 나왔다.
그래서 구글링을 통해 BFS 함수를 사용하는 방식으로 개선하고 제출하니 통과할 수 있었다.

1. 각 테스트 케이스 별로 그래프를 그려준다 (map)
2. 배추가 심어져 있는 위치를 1로 변경을 시켜준다.
3. 이차원배열로 되어있는 그래프를 탐색하면서 1을 찾는다.
4. 위치한 1을 기준으로 상하좌우를 탐색하여 모두 0으로 만들어준다.(BFS)
5. 필요한 벌레의 마리수를 +1 해준다.
6. 계속 반복한다.

DFS/BFS 그리고 그래프탐색에 내가 매우 약하다는것을 알게 해준 문제였고 직접 작성하던 코드에 BFS만 따로 구현하여 적용해보니 성장을 많이 할수 있었던 문제였다.