[JavaScript] 백준 골드 4 : 16234 - 인구 이동

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

16234번: 인구 이동

---

📌 작성한 코드 

// 16234
const fs = require("fs");
const filePath = process.platform === "linux" ? "/dev/stdin" : "Beakjoon/Gold/test.txt";
let input = fs.readFileSync(filePath).toString().trim().split("\n");

const [N, L, R] = input.shift().split(" ");
const board = input.map((str) => str.split(" ").map(Number));

const dx = [1, -1, 0, 0];
const dy = [0, 0, 1, -1];

const bfs = (a, b, visited) => {
    const queue = [];
    visited[a][b] = true;
    queue.push([a, b]);

    let flag = false;
    let total = 0;
    const temp = [[a, b]];

    let idx = 0;
    while (queue.length > idx) {
        const [x, y] = queue[idx++];
        total += board[x][y];

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

            if (nx < 0 || nx >= N || ny < 0 || ny >= N) continue;
            if (!visited[nx][ny]) {
                const differ = Math.abs(board[x][y] - board[nx][ny]);
                if (differ >= L && differ <= R) {
                    temp.push([nx, ny]);
                    flag = true;
                    visited[nx][ny] = true;
                    queue.push([nx, ny]);
                }
            }
        }
    }

    if (!flag) return flag;

    const avg = Math.floor(total / temp.length);
    temp.forEach(([x, y]) => {
        board[x][y] = avg;
    });

    return flag;
};

let answer = 0;
while (true) {
    let totalFlag = false;
    const visited = Array.from({ length: N }, () => new Array(N).fill(false));

    for (let i = 0; i < N; i++) {
        for (let j = 0; j < N; j++) {
            if (!visited[i][j]) {
                const flag = bfs(i, j, visited);
                if (flag) totalFlag = true;
            }
        }
    }
    if (!totalFlag) break;
    answer += 1;
}

console.log(answer);

 

📌풀이 

맞닿은 나라의 인구 차이가 일정 범위 안일 때 국경선을 허물고 인구 이동을 허용한다고 했을 때, 인구 이동을 멈추려면 며칠이 걸리는지 구하는 문제이다.  

 

(1) bfs를 통해 국경선을 허물 범위 구하기

- 현재 위치와 맞닿은 상하좌우의 인구 수를 확인하여 L이상 R이하인 경우 해당 방향의 국가와 국경선을 허문다.

- 국경선이 모두 허물어진 후에 해당 범위 안의 인원수의 평균으로 나눠진 인구를 갖게 만들어야 하므로, 국경선을 허물 때 해당 위치의 인구를 총 인구수에 더한다. 그리고 해당 위치의 값이 나중에 바뀌어야 하므로 해당 위치도 저장해준다 -> `temp`와 `total`에 저장한다.

- 해당 bfs를 돌렸을 때 국경선이 허물어지는 지를 확인하기 위해서 `flag`를 사용한다. 모든 위치를 확인하는 동안 flag가 바뀌지 않으면 더 이상 인구 이동이 없다는 의미이므로, 반복을 종료시키기 위해 필요하다.

- bfs를 통해 국경을 모두 허물고 나면 평균을 구해 해당 값으로 인구수를 업데이트 해준다. 

const bfs = (a, b, visited) => {
    const queue = [];
    visited[a][b] = true;
    queue.push([a, b]);

    let flag = false; // 인구 수가 바뀌는지 확인(국경선이 허물어져서 값이 바뀌는지)
    let total = 0; // 허문 국경 내의 총 인구수 
    const temp = [[a, b]]; // 국경선 내에 존재하는 나라들 좌표 -> 평균으로 업데이트하기 위해 필요함

    let idx = 0;
    while (queue.length > idx) {
        const [x, y] = queue[idx++];
        total += board[x][y]; // 총 인구수 더하기

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

            if (nx < 0 || nx >= N || ny < 0 || ny >= N) continue;
            if (!visited[nx][ny]) {
                const differ = Math.abs(board[x][y] - board[nx][ny]); 
                if (differ >= L && differ <= R) { // 둘의 인구수 차이가 범위 내면
                    flag = true; // 변경된 것을 확인하고
                    temp.push([nx, ny]); // (나중에 평균으로) 변경될 좌표를 저장해준다.
                    visited[nx][ny] = true;
                    queue.push([nx, ny]);
                }
            }
        }
    }

    if (!flag) return flag; // 변경된 것이 없으면 바로 리텅

    const avg = Math.floor(total / temp.length); // 평균 구하기
    temp.forEach(([x, y]) => {
        board[x][y] = avg; // 평균으로 위치 업데이트
    });

    return flag;
};

 

(2) 인구 이동 반복하기

- 아무런 인구 이동이 발생하지 않을 때까지  모든 좌표에 대해 인구 이동을 반복한다.

- 주의해야 할 점은 하루에 여러 곳에서 인구 이동이 발생 할 수 있으므로, 하루동안 visited를 공유해서 bfs를 적용한다. 하루가 지나고 나면 다시 인구 이동이 가능해지므로 visited를 초기화해서 새로 bfs를 적용한다. 

- 하루가 지날 때마다 답 + 1을 적용해서 정답을 구한다. 

let answer = 0;
while (true) { // 반복 1번당 하루
    let totalFlag = false;
    const visited = Array.from({ length: N }, () => new Array(N).fill(false)); // 중요!

	// 하루 동안(2중 반복 도는 동안) visited 공유해서 방문하지 않은 위치에서 인구 이동 시작하기
    for (let i = 0; i < N; i++) {
        for (let j = 0; j < N; j++) {
            if (!visited[i][j]) { 
                const flag = bfs(i, j, visited);
                if (flag) totalFlag = true;
            }
        }
    }
    if (!totalFlag) break;
    answer += 1;
}

console.log(answer);

 

✅ 성공