[백준 2667] 단지번호붙이기 with Node.js

문제 링크

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

2667번: 단지번호붙이기

풀이

const getCount = (start, visited, house) => {
  const offsetX = [-1, 0, 0, 1];
  const offsetY = [0, -1, 1, 0];
  const getXY = (idx) => [idx%N, Math.floor(idx/N)];
  const getIdx = (x, y) => x + y*N;
  const isValid = (x, y) => x >= 0 && x < N && y >= 0 && y < N;

  const stack = [start];
  const graph = [];
  let count = 0;

  while (stack.length) {
    const node = stack.pop();
    const [x, y] = getXY(node);
    if (!visited[node] && house[y][x] === '1') {
      visited[node] = true;
      graph.push(node);
      count++;
      offsetX.forEach((_, i) => {
        const [dx, dy] = [x + offsetX[i], y + offsetY[i]];
        const newNode = getIdx(dx, dy);
        if (isValid(dx, dy)) {
          stack.push(newNode);
        }
      });
    }
  }
  return count;
};

const solve = (N, house) => {
  const visited = new Array(N*N).fill(false);
  const output = [];
  visited.forEach((v, i) => {
    if (!v) {
      const count = getCount(i, visited, house);
      if (count > 0) output.push(count);
    }
  });
  console.log(output.length);
  console.log(output.sort((a, b) => a - b).join('\n'));
};

const [N, ...input] = require('fs').readFileSync('/dev/stdin').toString().trim().split('\n');
const house = input.map(row => row.split(''));
solve(N, house);

방문 여부를 나타내는 visited를 모두 false로 채우고 순회한다.

false일 경우 getCount에서 DFS를 통해 집의 개수를 세서 반환한다.

이 때 시작점이 집이 아니면 0을 반환하므로, count가 0보다 클 경우에만 output에 단지에 속한 집의 수를 저장한다.

 

DFS를 하면서 방문했던 곳의 visited를 true로 바꾸므로,

visited를 순회하면서 true인 곳은 지나치고 false인 곳에서 다시 getCount를 반복한다.

 

최종적으로 output의 개수와 output을 정렬한 각 원소를 출력한다.