[알고리즘/백준/16234] 인구 이동(BFS, Node.js)

문제

---

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

16234번: 인구 이동

 

풀이

---

이전에 풀었던 방식과 유사하지만 nodes라는 하나의 배열을 이용해 인구 이동을 조금 더 간단하게 구현하였다.

 

2중 for문으로 각각의 땅에서 BFS를 돌고 이동 가능한 경우 nodes 배열에 담아둔다. 

BFS가 끝나면 nodes 배열에 담긴 좌표들은 인구 이동을 해준다.

nodes 배열에 자기 자신만 담긴 경우(nodes.length === 1) 이동하지 못했다는 의미이므로 closedCount를 증가시킨다.

모든 땅을 다 돌고 난 이후 closedCount가 N*N이면 이동한 날짜인 day를 출력하고 종료한다. 

아닌 경우 하루를 증가시키고 계속해서 반복한다. 

 

class Queue {
  constructor() {
    this.data = [];
    this.head = 0;
    this.tail = 0;
  }
  push(item) {
    this.data[this.tail++] = item;
  }
  pop() {
    this.head++;
  }
  front() {
    return this.data[this.head];
  }
  rear() {
    return this.data[this.tail - 1];
  }
  isEmpty() {
    return this.head === this.tail;
  }
  size() {
    return Math.abs(this.head - this.tail);
  }
}

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

const [N, L, R] = input.split(" ").map(Number);
const map = arr.map((row) => row.split(" ").map(Number));
const dir = [
  [-1, 0],
  [1, 0],
  [0, -1],
  [0, 1],
];

let day = 0;

while (true) {
  const ch = Array.from({ length: N }, () => Array(N).fill(0));
  let closedCount = 0; // 인구 이동 불가능한 국가

  for (let i = 0; i < N; i++) {
    for (let j = 0; j < N; j++) {
      if (ch[i][j] === 1) continue;
      const nodes = []; // 인구 이동할 국가들
      const queue = new Queue();

      ch[i][j] = 1;
      queue.push([i, j]);
      nodes.push([i, j]);

      while (!queue.isEmpty()) {
        const [x, y] = queue.front();
        queue.pop();

        for (let k = 0; k < 4; k++) {
          const nx = x + dir[k][0];
          const ny = y + dir[k][1];

          if (nx < 0 || ny < 0 || nx >= N || ny >= N) continue;
          if (ch[nx][ny] === 1) continue;

          const diff = Math.abs(map[nx][ny] - map[x][y]);
          if (diff >= L && diff <= R) {
            ch[nx][ny] = 1;
            queue.push([nx, ny]);
            nodes.push([nx, ny]);
          }
        }
      }

      // bfs 끝났을 때
      const len = nodes.length;
      // 인구 이동 불가능한 경우
      if (len === 1) {
        closedCount += 1;
      } else {
      	// 인구 이동
        let sum = 0;
        for (let [x, y] of nodes) {
          sum += map[x][y];
        }
        const population = Math.floor(sum / len);
        for (let [x, y] of nodes) {
          map[x][y] = population;
        }
      }
    }
  }

  // 인구 이동이 불가능한 국가가 N * N인 경우 
  if (closedCount === N * N) {
    console.log(day);
    return;
  }

  day += 1;
}