인구 이동

인구 이동

문제 설명

N×N크기의 땅이 있고, 땅은 1×1개의 칸으로 나누어져 있다. 각각의 땅에는 나라가 하나씩 존재하며, r행 c열에 있는 나라에는 A[r][c]명이 살고 있다. 인접한 나라 사이에는 국경선이 존재한다. 모든 나라는 1×1 크기이기 때문에, 모든 국경선은 정사각형 형태이다.

오늘부터 인구 이동이 시작되는 날이다.

인구 이동은 하루 동안 다음과 같이 진행되고, 더 이상 아래 방법에 의해 인구 이동이 없을 때까지 지속된다.

국경선을 공유하는 두 나라의 인구 차이가 L명 이상, R명 이하라면, 두 나라가 공유하는 국경선을 오늘 하루 동안 연다.

위의 조건에 의해 열어야하는 국경선이 모두 열렸다면, 인구 이동을 시작한다.

국경선이 열려있어 인접한 칸만을 이용해 이동할 수 있으면, 그 나라를 오늘 하루 동안은 연합이라고 한다.

연합을 이루고 있는 각 칸의 인구수는 (연합의 인구수) / (연합을 이루고 있는 칸의 개수)가 된다. 편의상 소수점은 버린다.

연합을 해체하고, 모든 국경선을 닫는다.

각 나라의 인구수가 주어졌을 때, 인구 이동이 며칠 동안 발생하는지 구하는 프로그램을 작성하시오.

예제 입력

2 20 50
50 30
20 40

예제 출력

1

---

문제 풀이

const fs = require("fs");
const path = require("path");
const input = fs
  .readFileSync(
    process.platform === "linux"
      ? "/dev/stdin"
      : path.join(__dirname, "input.txt")
  )
  .toString()
  .trim()
  .split("\n");

const solution = (input) => {
  const [N, L, R] = input[0].split(" ").map(Number);
  const arr = input.slice(1).map((line) => line.split(" ").map(Number));
  const dx = [-1, 1, 0, 0];
  const dy = [0, 0, -1, 1];
  const move = (union) => {
    // 연합의 인구 수 더하기
    let sum = 0;
    let len = union.length;
    for ([x, y] of union) {
      sum += arr[x][y];
    }
    let avg = Math.floor(sum / len);
    // 연합 인구 바꾸기
    for ([x, y] of union) {
      arr[x][y] = avg;
    }
  };

  const bfs = (i, j, visited) => {
    visited[i][j] = true;
    // queue 와 연합 배열 정의
    let queue = [[i, j]];
    let union = [[i, j]];
    let head = 0;

    while (queue.length > head) {
      const [x, y] = queue[head++];

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

        if (0 <= nx && nx < N && 0 <= ny && ny < N && !visited[nx][ny]) {
          //인접한 곳의 절대값 계산
          const diff = Math.abs(arr[x][y] - arr[nx][ny]);
          // 절대값 기준 통과시
          if (L <= diff && diff <= R) {
            // 다음 좌표 큐에 넣고 연합 좌표에 추가
            queue.push([nx, ny]);
            union.push([nx, ny]);
            // 방문 체크
            visited[nx][ny] = true;
          }
        }
      }
    }
    return union;
  };
  let year = 0;
  while (true) {
    // 방문 체크 배열
    let visited = Array.from({ length: N }, () => Array(N).fill(false));
    // 인구 이동이 일어 날 수 있는 지 체크 변수
    let moved = false;
    for (let i = 0; i < N; i++) {
      for (let j = 0; j < N; j++) {
        if (!visited[i][j]) {
          // 연합 생성
          const union = bfs(i, j, visited);
          // 연합이 만들어졌으면
          if (union.length > 1) {
            // 이동 가능 체크 후
            moved = true;
            // 실제 이동
            move(union);
          }
        }
      }
    }
    // 이동이 일어나지 않으면 탈출
    if (!moved) break;
    // 해 증가
    year++;
  }
  console.log(year);
};

solution(input);

아이디어 / 접근법

1. 실제로 인구가 이동하는 함수
2. BFS 를 통한 연합 배열 생성
3. while 문으로 연합 생성하고 해당 연합에 속한 나라가 1이 넘는다며(단독 연합이 아니라면) 이동가능하다고 보고 실제 이동시키기
4. 그러고 얼마나 걸렸는 지 출력하기

후기

진짜 개인적으로 엄청 어려웠다고 생각했음 이것도 따지고보면 요구사항대로 차근차근 구현하면 되는 문제인데 그냥 되게 어려웠던 것 같음