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

문제

---

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

16234번: 인구 이동

 

풀이

---

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 [n, ...arr] = fs.readFileSync(filePath).toString().trim().split("\n");
const [N, L, R] = n.split(" ").map(Number);
const countries = arr.map((row) => row.split(" ").map(Number));
const dir = [
  [-1, 0],
  [0, 1],
  [1, 0],
  [0, -1],
];

let answer = 0;
while (true) {
  // 경계 공유하는 각 영역
  const units = Array.from({ length: N }, () => Array(N).fill(0));
  const ch = Array.from({ length: N }, () => Array(N).fill(0));
  // 각 unit에 해당하는 index에 [total, len] 저장
  const unitResult = Array.from({ length: N * N }, () => [0, 0]);
  let currentUnit = 0;
  let total = 0;

  for (let i = 0; i < N; i++) {
    for (let j = 0; j < N; j++) {
      // 방문하지 않은 경우 각 unit 찾기
      if (ch[i][j] === 1) continue;

      const q = new Queue();
      q.push([i, j]);
      ch[i][j] = 1;
      units[i][j] = currentUnit;
      unitResult[currentUnit][0] += countries[i][j];
      unitResult[currentUnit][1] += 1;

      while (!q.isEmpty()) {
        const [x, y] = q.front();
        q.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;

          const diff = Math.abs(countries[x][y] - countries[nx][ny]);

          if (diff >= L && diff <= R && ch[nx][ny] === 0) {
            ch[nx][ny] = 1;
            units[nx][ny] = currentUnit;
            unitResult[currentUnit][0] += countries[nx][ny];
            unitResult[currentUnit][1] += 1;
            q.push([nx, ny]);
          }
        }
      }

      currentUnit++;
    }
  }

  // units 배열 기준으로 countries 배열의 인구수 변경
  for (let i = 0; i < N; i++) {
    for (let j = 0; j < N; j++) {
      // units[i][j]의 값은 countries[i][j]의 영역을 의미
      // 따라서, units[i][j]가 0이면 -> unitResult[0][0]/unitResult[0][1] 값을 넣어주기
      const idx = units[i][j];
      total += idx;
      countries[i][j] = Math.floor(unitResult[idx][0] / unitResult[idx][1]);
    }
  }
  if (total === (N * N * (N * N - 1)) / 2) {
    console.log(answer);
    return;
  }
  answer++;
}

NxN의 땅에 국가가 1x1크기로 있고, 인접한 나라 사이에는 국경선이 존재한다. 

인접한 국가의 인구 차이가 L명 이상 R명 이하라면 국경선을 하루동안 열고, 하루동안 인구 이동을 한다. 

인구 이동을 하면 해당 조건을 만족하는 모든 국가는 소수점을 버린 (연합 인구 수)/(연합을 이루고 있는 칸의 개수)개로 인구가 변경된다. 

그리고 인구 이동이 가능할 때까지 이를 반복할 때 며칠 동안 인구이동이 발생하는지를 구해야 한다. 

 

이 문제는 아래의 두 단계를 인구 이동이 불가능할 때까지 반복하면 된다.

1.  국가 배열을 BFS로 돌면서 인구 이동이 가능한 영역을 기록한다. 

2.  1에서 찾은 영역을 바탕으로 인구 이동 후 인구수를 계산해 각 영역에 넣어준다. 

 

조금 더 자세히 각 단계를 살펴보면 아래와 같다.

1. 국가 배열을 BFS로 돌면서 인구 이동이 가능한 영역을 기록한다. 

  1-1. 각 영역은 NxN 크기의 units 배열에 저장한다. 새로운 영역을 찾을 때마다 currentUnit을 1씩 증가시키면서 BFS로 탐색할 수 있는 새로운 영역임을 표시한다. currentUnit은 0부터 시작한다. 

  1-2. unitResult는 각 currentUnit(자신의 영역)에 해당하는 인구수를 알기 위해 [전체 연합 인구 수, 전체 연합 국가 개수]를 저장한다. 처음 q에 넣을 때, 그리고 조건을 만족하는 국가를 찾았을 때 국가 배열(countries)의 해당 위치 인구수를 더해주고, 국가 개수를 증가시킨다. 그리고 방문했던 국가는 다시 가지 않도록 ch 배열에 방문 표시(중요!!)를 한다. 

  1-3. 가능한 영역 하나를 모두 돌고 나면 해당 q가 비워지면서 탐색을 종료한다. 이때 다음 unit으로 넘어가기 위해 currentUnit을 1 증가시킨다. 

 

2.  1에서 찾은 영역을 바탕으로 인구 이동 후 인구수를 계산해 각 영역에 넣어준다. 

  2-1. units 배열에는 각 국가가 해당하는 영역이 저장되어있다. unitResult  배열에는 각 영역에 해당하는 전체 인구 수와 전체 국가 개수가 저장되어있다. 2중 for문을 돌면서 countries의 인구수를 변경시킨다. countries[i][j]가 해당하는 영역을 units 배열에서 찾고, 해당 영역의 연합 인구수를 unitResult 배열을 통해 계산한다. 

  2-2. 이때 멈추는 조건은 인구이동을 더 이상 할 수 없을 때이다. 그때는 각 국가가 모두 자신의 영역을 가지기 때문에 units 배열이 [[0, 1, 2], [3, 4, 5], [6, 7, 8]]과 같이 저장된다. 따라서 전체 값을 더하면 0~n*n-1까지를 더한 값과 같을 때 answer을 콘솔에 찍고 함수를 종료한다. 

  2-3. answer은 BFS로 영역을 표시하고, 해당 영역의 인구수를 모두 변경하는 이 전 과정이 끝났을 때 하루가 지났다는 의미에서 1을 증가시킨다. 

  2-4. 인구이동이 가능하다면 1~2를 while문에서 반복한다. 

 

 

 

이번에 풀면서 실수하거나 어려웠던 점들.. ! 

• q에 초기값을 넣어줄 때 ch 배열에 체크하고, units, unitResult에 표시해주지 않았다.
• 변수를 어디에서 초기화시켜줄지가 헷갈렸다. 이 부분은 어디에서 해당 변수와 관계 있는 연산이 끝나고 시작하는지를 잘 생각해야 할 것 같다.
• 또 unitResult에 숫자를 더해줄 때 처음에 NaN이 나왔는데 배열을 []로 초기화해 undefined + 1을 해서 그랬다. [0, 0]으로 숫자로 초기화시켜줘야 했다. 
• 이런 유형이 나오면 bfs로 필요한 영역을 찾고 그 결과를 바탕으로 필요한 작업을 해야겠다.