🎲 백준 16234번 인구 이동 [JS]

🧶 풀이
인구 이동을 영역나누기라고 생각하면 편하다.
단순 영역 나누기와 다른점 :
1. 국경선을 공유하는 나라를 따로 저장하기 (changePoints)
2. dfs를 수행하고 나서 changePoints에 저장된 좌표의 값을 새로운 인구수로 업데이트 해준다.
위 과정이 수행되면 하루가 지난 것이다. change 변수로 인구이동이 일어났는지 여부를 확인하고 while 반복문을 수행한다.

코드

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

let answer = 0;

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

const dfs = (i, j, changePoints, visited) => {
  const stack = [[i, j]];
  visited[i][j] = true;
  let value = 0;

  while (stack.length) {
    let [Y, X] = stack.pop();
    value += arr[Y][X];
    changePoints.push([Y, X]);

    for (let d = 0; d < 4; d++) {
      const [nextY, nextX] = [Y + dir[d][0], X + dir[d][1]];
      if (
        nextY < 0 ||
        nextX < 0 ||
        nextY >= N ||
        nextX >= N ||
        visited[nextY][nextX] ||
        Math.abs(arr[Y][X] - arr[nextY][nextX]) < L ||
        Math.abs(arr[Y][X] - arr[nextY][nextX]) > R
      )
        continue;

      stack.push([nextY, nextX]);
      visited[nextY][nextX] = true;
    }
  }

  return value;
};

let change = true;

while (change) {
  let visited = Array.from(new Array(N), () => new Array(N).fill(false));
  change = false;

  for (let i = 0; i < N; i++) {
    for (let j = 0; j < N; j++) {
      const changePoints = [];
      if (!visited[i][j]) {
        let changeValue = dfs(i, j, changePoints, visited);
        for (let c = 0; c < changePoints.length; c++) {
          const [y, x] = changePoints[c];
          arr[y][x] = Math.floor(changeValue / changePoints.length);
        }
        if (changePoints.length > 1) change = true;
      }
    }
  }

  if (change) answer++;
}

console.log(answer);