[BOJ 16234] 인구 이동

문제

인구 이동

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

 

 

풀이

설명

인구 이동이 며칠 동안 발생하는지를 구하는 문제입니다.

 

규칙은 다음과 같습니다.

1. 국경선을 공유하는 두 나라의 인구 차이가 L명 이상, R명 이하라면, 두 나라가 공유하는 국경선을 오늘 하루 동안 엽니다.
2. 위의 조건에 의해 열어야하는 국경선이 모두 열렸다면, 인구 이동을 시작합니다.
3. 국경선이 열려있어 인접한 칸만을 이용해 이동할 수 있으면, 그 나라를 오늘 하루 동안은 연합이라고 합니다.
4. 연합을 이루고 있는 각 칸의 인구수는 (연합의 인구수) / (연합을 이루고 있는 칸의 개수)가 됩니다. 편의상 소수점은 버립니다.
5. 연합을 해체하고, 모든 국경선을 닫습니다.

 

그래프 탐색을 이용해 해결할 수 있습니다.

 

예시 코드

function solution() {
  const [N, L, R] = input().split(" ").map(Number);
  const A = Array.from({ length: N }, () => input().split(" ").map(Number));
  const dx = [-1, 1, 0, 0];
  const dy = [0, 0, -1, 1];
  const visited = Array.from({ length: N }, () => Array(N).fill(false));
  let days = 0;

  while (true) {
    let moved = false;

    for (let i = 0; i < N; i++) {
      visited[i].fill(false);
    }

    for (let i = 0; i < N; i++) {
      for (let j = 0; j < N; j++) {
        if (visited[i][j]) continue;
        const union = [];
        visited[i][j] = true;
        const population = dfs(i, j, union);

        if (union.length > 1) {
          redistributePopulation(union, population);
          moved = true;
        }
      }
    }

    if (!moved) break;
    days++;
  }

  return days;

  function dfs(x, y, union) {
    union.push([x, y]);
    let population = A[x][y];

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

      if (!isValidCoord(nx, ny)) continue;
      if (visited[nx][ny]) continue;
      if (!canUnite(x, y, nx, ny)) continue;

      visited[nx][ny] = true;
      population += dfs(nx, ny, union);
    }

    return population;
  }

  function isValidCoord(x, y) {
    return x >= 0 && x < N && y >= 0 && y < N;
  }

  function canUnite(x, y, nx, ny) {
    const diff = Math.abs(A[x][y] - A[nx][ny]);
    return diff >= L && diff <= R;
  }

  function redistributePopulation(union, totalPopulation) {
    const newPopulation = Math.floor(totalPopulation / union.length);
    for (const [x, y] of union) {
      A[x][y] = newPopulation;
    }
  }
}