https://www.acmicpc.net/problem/16234
16234번: 인구 이동
N×N크기의 땅이 있고, 땅은 1×1개의 칸으로 나누어져 있다. 각각의 땅에는 나라가 하나씩 존재하며, r행 c열에 있는 나라에는 A[r][c]명이 살고 있다. 인접한 나라 사이에는 국경선이 존재한다. 모
www.acmicpc.net
📌 작성한 코드
// 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);
✅ 성공

'알고리즘 > 백준' 카테고리의 다른 글
| [JavaScript] 백준 골드 5 : 21608 - 상어 초등학교 (1) | 2024.02.13 |
|---|---|
| [JavaScript] 백준 골드 5 : 20055 - 컨베이어 벨트 위의 로봇 (1) | 2024.02.11 |
| [JavaScript] 백준 골드 5 : 14891 - 톱니바퀴 (1) | 2024.02.11 |
| [JavaScript] 백준 골드 5 : 15686 - 치킨 배달 (1) | 2024.02.09 |
| [JavaScript/백트래킹] 백준 실버 1 : 14889 - 스타트와 링크 (2) | 2024.02.08 |