인구 이동 (백준 16234)

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

16234번: 인구 이동

 

🚀문제 해석

1. DFS 그래프 탐색을 하면서 인구 수의 차이가 주어진 범위를 만족하는지 확인한다. 만족을 한다면 V배열에 담아준다.

만약 V배열의 길이가 1이면 인접한 나라와의 인구수 차이가 범위를 만족하지 않는 것이다. 이때는 다른 나라로 넘어가 DFS 탐색을 해야한다.

 

2. 만약 V배열의 길이가 2 이상이면 업데이트할 인구수를 계산한다.

수식은  (연합의 인구수) / (연합을 이루고 있는 칸의 개수)

그리고 flag 변수를 이용해서 인구 이동을 했다는 표시를 한다.

 

3. 인구이동이 이루어졌으면 ret를 ++

 

4. 과정을 반복한다. 만약 !flag 이면 반복을 종료하고 ret를 return 한다.

🛠코드

dfs 함수에 v 배열을 넘겨주는 아이디어가 핵심이었다.

let [a, ...map] = require('fs').readFileSync(0).toString().trim().split('\n');
let [n, l, r] = a.split(' ').map(Number);
map = map.map((elem) => elem.split(' ').map(Number));

function solution() {
  let check;
  const dy = [-1, 0, 1, 0];
  const dx = [0, 1, 0, -1];
  let ret = 0;

  function dfs(y, x, v) {
    for (let i = 0; i < 4; i++) {
      const ny = y + dy[i];
      const nx = x + dx[i];
      if (ny < 0 || ny >= n || nx < 0 || nx >= n || check[ny][nx]) continue;
      if (Math.abs(map[y][x] - map[ny][nx]) >= l && Math.abs(map[y][x] - map[ny][nx]) <= r) {
        check[ny][nx] = 1;
        v.push([ny, nx]);
        dfs(ny, nx, v);
      }
    }
  }

  while (true) {
    let flag = 0;
    check = Array.from({ length: n }, () => Array.from({ length: n }).fill(0));
    for (let i = 0; i < map.length; i++) {
      for (let j = 0; j < map[0].length; j++) {
        if (!check[i][j]) {
          check[i][j] = 1;
          let v = [];
          v.push([i, j]);
          dfs(i, j, v);
          if (v.length === 1) continue;
          let sum = 0;
          for (const [y, x] of v) {
            sum += map[y][x];
          }
          let update = Math.floor(sum / v.length);
          for (const [y, x] of v) {
            map[y][x] = update;
          }
          flag = 1;
        }
      }
    }
    if (!flag) break;
    ret++;
  }

  return ret;
}

console.log(solution());