[백준 16234 - Node.js] 인구 이동

🔗 문제 링크

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

16234번: 인구 이동

✏️ 풀이

const input = require('fs').readFileSync('/dev/stdin').toString().trim().split('\n');
const [N, L, R] = input.shift().split(' ').map(Number);
const land = input.map(v => v.split(' ').map(Number));

const offset = [[0, 1], [1, 0], [0, -1], [-1, 0]];
const dfs = (start, visited) => {
  const stack = [start];
  const union = [start];
  const [sx, sy] = start;
  visited[sx][sy] = true;
  let population = land[sx][sy];
  while (stack.length) {
    const [x, y] = stack.pop();
    for (let i = 0; i < 4; i++) {
      const nx = x + offset[i][0];
      const ny = y + offset[i][1];
      if (nx >= 0 && nx < N && ny >= 0 && ny < N && !visited[nx][ny]) {
        const diff = Math.abs(land[x][y] - land[nx][ny]);
        if (diff >= L && diff <= R) {
          stack.push([nx, ny]);
          population += land[nx][ny];
          visited[nx][ny] = true;
          union.push([nx, ny]);
        }
      }
    }
  }
  union.forEach(([x, y]) => land[x][y] = Math.floor(population / union.length));
  return union.length;
};

let day = 0;
while (true) {
  const visited = [...Array(N)].map(() => Array(N).fill(false));
  let flag = false;
  for (let i = 0; i < N; i++) {
    for (let j = 0; j < N; j++) {
      if (!visited[i][j]) {
        const unionCount = dfs([i, j], visited);
        if (unionCount > 1) {
          flag = true;
        }
      }
    }
  }
  if (!flag) {
    break;
  }
  day++;
}

console.log(day);

모든 국가를 순회하면서 열 수 있는 모든 국경선을 연다. 국경선을 열 수 있다는 것은 현재 국가에서 국경선을 맞댄 다른 국가로 이동할 수 있다는 뜻이므로, 순회를 시작한 국가에서부터 이동할 수 있는 모든 국가를 다 탐색해서 하나의 연합을 형성할 수 있다. 인접 국가들을 탐색하면서 인구 비교를 통해 연합에 속하는 국가들을 알아내고, 그 국가들의 인구수를 (인구 수 합) / (국가 수)로 갱신한다. 

 

인구수를 갱신하는 시점이 문제에 따르면 모든 국경선이 열린 후이지만, visited로 방문 처리를 해주고 있기 때문에 중복 방문의 가능성이 없어서 하나의 연합에 속하는 국가를 모두 탐색할 때마다 갱신해줘도 문제가 되지 않는다.

 

이렇게 해서 모든 국가를 순회하여 연합을 찾고 모든 연합의 인구수를 갱신하였다. 인구수를 갱신하였다는 것은 인구 이동이 일어났다는 뜻이므로, 인구 이동이 일어난 일수(day)를 증가시킨다. 그리고 while문은 다시 이 과정을 인구 이동이 단 한 번도 일어나지 않을 때까지 반복한다.

 

만약, 모든 연합에 국가가 단 1개씩만 속해 있다면, 이것은 국경선이 단 하나도 열리지 않았다는 것을 의미하고, 결국 인구 이동이 없다는 뜻이다. 따라서, 각 연합에 국가가 몇 개씩 속해 있는지를 확인해서 단 한 번도 2개 이상 속한 적이 없다면 while문을 빠져나온다. 

 

dfs 함수에서는 탐색이 끝나고 인구수를 갱신하고, while문에서 인구 이동 여부를 확인하기 쉽도록 연합에 속한 국가의 수를 반환하도록 하였다.