[백준 4963] 섬의 개수 with Node.js

문제 링크

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

4963번: 섬의 개수

풀이

const input = require('fs').readFileSync('/dev/stdin').toString().trim().split('\n');
const iterator = input[Symbol.iterator]();
const dfs = (w, h, arr, visited, start) => {
  const offsetX = [-1, 0, 1, -1, 1, -1, 0, 1];
  const offsetY = [-1, -1, -1, 0, 0, 1, 1, 1];
  const stack = [start];
  while (stack.length) {
    const node = stack.pop();
    if (!visited[node]) {
      visited[node] = true;
      const [ x, y ] = [ node%w, Math.floor(node/w) ];
      offsetX.forEach((_, i) => {
        const [ dx, dy ] = [ x + offsetX[i], y + offsetY[i] ];
        const newNode = dx + dy*w;
        if (dx >= 0 && dx < w && dy >= 0 && dy < h && !visited[newNode] && arr[dy][dx]) {
          stack.push(newNode);
        }
      });
    }
  }
};

while (true) {
  const iterResult = iterator.next();
  if (iterResult.value === '0 0') break;
  const [ w, h ] = iterResult.value.split(' ').map(v => +v);
  const arr = [];
  const visited = new Array(w*h).fill(false);
  let count = 0;
  for (let i=0; i<h; i++) {
    arr.push(iterator.next().value.split(' ').map(v => +v));
  }
  for (let i=0; i<w*h; i++) {
    if (!visited[i] && arr[Math.floor(i/w)][i%w]) {
      dfs(w, h, arr, visited, i);
      count++;
    }
  }
  console.log(count);
}

그래프의 연결 요소(Connected Component)의 개수를 묻는 문제이므로,

visited를 순회하면서 아직 방문하지 않은 땅에 대해 dfs를 실행하고 그 횟수를 출력한다.

 

이렇게 하면 어떤 섬의 땅 하나에서 dfs를 실행하여 그 섬의 모든 땅을 방문하고,

계속 visited 순회를 진행하면서 새로운 섬의 땅 하나에서 또 dfs를 실행하게 된다.

따라서, dfs를 실행한 횟수가 곧 섬의 개수이다.

 

dfs에서는 가로 세로 대각선 8개 방향에 대해 아직 방문하지 않은 땅이면 stack에 push하여 방문하도록 하였다.