백준 2667 단지번호 붙이기

문제

단지를 정의하고 각 단지에 속하는 집의 수를 오름차순으로 정렬하여 출력하는 그래프 탐색 문제이다. 나는 먼저 dfs가 익숙하므로 dfs로 풀어보았다.

const INPUT_FILE = process.platform === "linux" ? "/dev/stdin" : "./inputs.txt";
const [n, ...m] = require("fs")
  .readFileSync(INPUT_FILE)
  .toString()
  .trim()
  .split("\n");
const N = +n;
const houseMap = m.map((h) => Array.from(h).map(Number));
const dLoc = [
  [-1, 0],
  [0, -1],
  [1, 0],
  [0, 1],
];
let houses = 0;
const result = [];
for (let i = 0; i < N; i++) {
  for (let j = 0; j < N; j++) {
    if (houseMap[i][j]) {
      dfs(i, j);
      result.push(houses);
      houses = 0;
    }
  }
}
console.log(result.length);
console.log(result.sort((a, b) => a - b).join("\n"));
 
function dfs(x, y, count = 0) {
  houseMap[x][y] = 0;
  houses++;
  for (const [dx, dy] of dLoc) {
    if (
      x + dx >= 0 &&
      x + dx < N &&
      y + dy >= 0 &&
      y + dy < N &&
      houseMap[x + dx][y + dy]
    ) {
      dfs(x + dx, y + dy, count + 1);
    }
  }
}
 

지나간 집의 경우는 0으로 바꾸면서 dfs 탐색을 실행했다. 특이한 점으로는 houses를 전역으로 두고 한번 dfs 탐색이 끝날 때마다 초기화해주는 방식으로 갔는데, 이것보다는 함수 내에서 관리해서 리턴받고 결과에 push하는 방식이 더 나을 것 같다.

function dfs(x, y) {
  houseMap[x][y] = 0;
  let count = 1;
  for (const [dx, dy] of dLoc) {
    if (
      x + dx >= 0 &&
      x + dx < N &&
      y + dy >= 0 &&
      y + dy < N &&
      houseMap[x + dx][y + dy]
    ) {
      count += dfs(x + dx, y + dy);
    }
  }
  return count;
}

dfs 함수를 이런 식으로 따로 count를 넘기는게 아니라 각 함수에서 클로저로 관리하면서 dfs 탐색 과정에서 count값을 계속 더한 다음 반환하도록 했다. 이런 식으로 하면 가장 처음 실행된 dfs 함수에서 모든 dfs 탐색이 끝난 뒤의 count를 받아올 수 있게 된다. 이 결과를 그냥 결과 배열에 넣으면 된다.

function bfs(x, y) {
  let count = 1;
  const queue = [[x, y]];
  houseMap[x][y] = 0;
 
  while (queue.length) {
    const [cx, cy] = queue.shift();
    for (const [dx, dy] of dLoc) {
      const nx = cx + dx,
        ny = cy + dy;
      if (nx >= 0 && nx < N && ny >= 0 && ny < N && houseMap[nx][ny]) {
        houseMap[nx][ny] = 0;
        queue.push([nx, ny]);
        count++;
      }
    }
  }
  return count;
}

bfs 방식으로도 시도해 보았다. bfs 방식은 처음 실행된 쪽에서 방향을 찾아 계속 들어가는 dfs 방식이 아닌, 가능한 방향을 먼저 모두 받고 하나씩 큐에서 빼내가면서 모든 방향에 대해 먼저 탐색하는 과정을 거친다.

해당 문제는 계속 한쪽으로 깊게 들어가는 구조보다는 여러 방향으로 단지가 구성되어있는 경우가 많다고 생각하기 때문에 dfs보다는 bfs가 더 적절할 것 같다.

위에가 bfs로 실행했을 때이고, 아래가 dfs로 실행했을 때이다. 시간적으로 bfs가 빠른 속도를 보여준다.