[boj] 2667. 단지번호붙이기 (node.js)

요약

2667

• 입력: 그래프를 구성하는 단지들의 N*N 행렬
• 출력: 총 단지의 수, 단지에 속하는 집의 수
• 연결되어 있는 집들끼리 한 단지를 이룬다. 이때, 단지의 총 개수와 각 단지를 이루는 집의 수를 오름차순으로 출력하라.

풀이

문제에서 주는 값이 인접 행렬이므로, 인접 행렬 형태로 그래프 데이터를 집어넣고, visited 배열을 생성해 DFS를 수행하였다. 방문하지 않았고 집이 있는 단지에서 시작해, dfs함수를 재귀적으로 호출한다. dfs 문이 새로 시작될 때마다 총 단지의 수는 +1 하고, 단지를 이루는 집의 수는 0으로 초기화한 후 dfs를 수행하여 문제에서 원하는 값을 출력한다.

내 풀이

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

let cnt = 0;
const input = () => stdin[cnt++];

const dir = [
  [0, 1],
  [1, 0],
  [0, -1],
  [-1, 0],
];

let stdin = [];
rl.on("line", function (line) {
  stdin.push(line);
}).on("close", function () {
  const N = Number(input());
  const arr = new Array(N);
  const visited = new Array(N);
  for (let i = 0; i < N; i++) {
    arr[i] = input();
    visited[i] = new Array(N).fill(0);
  }

  let count,
    total = 0,
    result = [];
  for (let i = 0; i < N; i++) {
    for (let j = 0; j < N; j++) {
      if (arr[i][j] == "1" && !visited[i][j]) {
        total++;
        count = 0;
        dfs(i, j);
        result.push(count);
      }
    }
  }
  console.log(total);
  result.sort((a, b) => a - b).forEach((x) => console.log(x));

  function dfs(x, y) {
    visited[x][y] = 1;
    count++;
    for (let i = 0; i < 4; i++) {
      nx = x + dir[i][0];
      ny = y + dir[i][1];
      if (arr[nx] == undefined) continue;
      if (arr[nx][ny] == "1" && !visited[nx][ny]) dfs(nx, ny);
    }
  }
  process.exit();
});

• 모든 탐색이 끝난 후, 문제 조건에 따라 각 단지를 이루는 집의 개수는 오름차순으로 출력해야 한다.