[백준] 16234 인구이동 - javascript
📌 문제
https://www.acmicpc.net/problem/16234
📌 풀이
const fs = require('fs');
const filePath = process.platform === 'linux' ? '/dev/stdin' : 'input.txt';
let input = fs.readFileSync(filePath).toString().trim().split('\n');
const [n, l, r] = input.shift().split(' ').map(Number);
const citys = Array.from({ length: n }, () => Array.from({ length: n }, () => 0));
for (let i = 0; i < n; i++) {
citys[i] = input.shift().split(' ').map(Number);
}
let ans = 0;
const dx = [0, 0, 1, -1];
const dy = [1, -1, 0, 0];
while (1) {
let flag = false;
const visited = Array.from({ length: n }, () => Array.from({ length: n }, () => false));
for (let i = 0; i < n; i++) {
for (let j = 0; j < n; j++) {
if (!visited[i][j]) {
let queue = [[i, j]];
let visitedRecord = [[i, j]];
let cnt = 1;
let sumPopulation = citys[i][j];
visited[i][j] = true;
while (queue.length) {
const [x, y] = queue.shift();
for (let k = 0; k < 4; k++) {
const [nx, ny] = [x + dx[k], y + dy[k]];
if (nx >= 0 && nx < n && ny >= 0 && ny < n) {
const diff = Math.abs(citys[x][y] - citys[nx][ny]);
if (diff >= l && diff <= r && !visited[nx][ny]) {
visited[nx][ny] = true;
queue.push([nx, ny]);
visitedRecord.push([nx, ny]);
cnt++;
sumPopulation += citys[nx][ny];
flag = true;
}
}
}
}
const changePopulation = Math.floor(sumPopulation / cnt);
for (const [x, y] of visitedRecord) {
citys[x][y] = changePopulation;
}
}
}
}
if (!flag) break;
ans += 1;
}
console.log(ans);
✔ 알고리즘 : BFS + 구현
✔ 0,0부터 2중 for문을 통해 순회하며 국경선을 열 수 있는지를 판단한다.
✔ visitedRecord 배열을 통해 현재 국경이 열려져있는, 즉 이어져있는 도시의 개수를 cnt로 갱신해나간다.
✔ BFS 함수 부분에서 queue.length까지 탐색이 끝나면 인구 이동을 시작한다.
✔ 한번이라도 국경을 열 수 있으면 flag를 true로 이중 for문을 돌았는데 인구 이동이 한번도 없다면 flag가 초기값인 false이기 때문에 while문이 종료된다. 👉 인구이동 종료
✔ 난이도 : 백준 기준 골드 5
Author And Source
이 문제에 관하여([백준] 16234 인구이동 - javascript), 우리는 이곳에서 더 많은 자료를 발견하고 링크를 클릭하여 보았다 https://velog.io/@ywc8851/백준-16234-인구이동-javascript저자 귀속: 원작자 정보가 원작자 URL에 포함되어 있으며 저작권은 원작자 소유입니다.
우수한 개발자 콘텐츠 발견에 전념 (Collection and Share based on the CC Protocol.)