[백준] 16234 인구이동 - javascript

📌 문제

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

📌 풀이

const fs = require('fs');
const filePath = process.platform === 'linux' ? '/dev/stdin' : 'input.txt';
let input = fs.readFileSync(filePath).toString().trim().split('\n');

const [n, l, r] = input.shift().split(' ').map(Number);
const citys = Array.from({ length: n }, () => Array.from({ length: n }, () => 0));

for (let i = 0; i < n; i++) {
  citys[i] = input.shift().split(' ').map(Number);
}

let ans = 0;
const dx = [0, 0, 1, -1];
const dy = [1, -1, 0, 0];

while (1) {
  let flag = false;
  const visited = Array.from({ length: n }, () => Array.from({ length: n }, () => false));

  for (let i = 0; i < n; i++) {
    for (let j = 0; j < n; j++) {
      if (!visited[i][j]) {
        let queue = [[i, j]];
        let visitedRecord = [[i, j]];
        let cnt = 1;
        let sumPopulation = citys[i][j];
        visited[i][j] = true;

        while (queue.length) {
          const [x, y] = queue.shift();
          for (let k = 0; k < 4; k++) {
            const [nx, ny] = [x + dx[k], y + dy[k]];

            if (nx >= 0 && nx < n && ny >= 0 && ny < n) {
              const diff = Math.abs(citys[x][y] - citys[nx][ny]);
              if (diff >= l && diff <= r && !visited[nx][ny]) {
                visited[nx][ny] = true;
                queue.push([nx, ny]);
                visitedRecord.push([nx, ny]);
                cnt++;
                sumPopulation += citys[nx][ny];
                flag = true;
              }
            }
          }
        }

        const changePopulation = Math.floor(sumPopulation / cnt);

        for (const [x, y] of visitedRecord) {
          citys[x][y] = changePopulation;
        }
      }
    }
  }

  if (!flag) break;
  ans += 1;
}
console.log(ans);

✔ 알고리즘 : BFS + 구현

✔ 0,0부터 2중 for문을 통해 순회하며 국경선을 열 수 있는지를 판단한다.

✔ visitedRecord 배열을 통해 현재 국경이 열려져있는, 즉 이어져있는 도시의 개수를 cnt로 갱신해나간다.

✔ BFS 함수 부분에서 queue.length까지 탐색이 끝나면 인구 이동을 시작한다.

✔ 한번이라도 국경을 열 수 있으면 flag를 true로 이중 for문을 돌았는데 인구 이동이 한번도 없다면 flag가 초기값인 false이기 때문에 while문이 종료된다. 👉 인구이동 종료

✔ 난이도 : 백준 기준 골드 5