[백준] 2146 다리 만들기 - javascript
📌 문제
https://www.acmicpc.net/problem/2146
📌 풀이
const fs = require('fs');
const filePath = process.platform === 'linux' ? '/dev/stdin' : 'input.txt';
let input = fs.readFileSync(filePath).toString().trim().split('\n');
const n = +input.shift();
const dx = [0, 0, 1, -1];
const dy = [1, -1, 0, 0];
let board = input.map((i) => i.split(' ').map(Number));
let visited = Array.from(Array(n), () => Array(n).fill(false));
let islandCnt = 0;
function check(x, y) {
return 0 <= x && x < n && 0 <= y && y < n;
}
function dfs(x, y, islandCnt) {
visited[x][y] = true;
board[x][y] = islandCnt;
for (let i = 0; i < 4; i++) {
let nx = x + dx[i];
let ny = y + dy[i];
if (check(nx, ny) && board[nx][ny] && !visited[nx][ny]) dfs(nx, ny, islandCnt);
}
}
for (let i = 0; i < n; i++) {
for (let j = 0; j < n; j++) {
if (board[i][j] && !visited[i][j]) dfs(i, j, ++islandCnt);
}
}
function bfs(islandCnt) {
let queue = [];
visited = Array.from(Array(n), () => Array(n).fill(0));
for (let i = 0; i < n; i++) {
for (let j = 0; j < n; j++)
if (board[i][j] == islandCnt) {
visited[i][j] = 1;
queue.push([i, j]);
}
}
let cnt = 0;
while (queue.length) {
let qlen = queue.length;
while (qlen--) {
let cur = queue.shift();
let x = cur[0];
let y = cur[1];
for (let i = 0; i < 4; i++) {
let nx = x + dx[i];
let ny = y + dy[i];
if (!check(nx, ny)) continue;
if (board[nx][ny] !== 0 && board[nx][ny] !== islandCnt) return cnt;
if (board[nx][ny] === 0 && !visited[nx][ny]) {
visited[nx][ny] = 1;
queue.push([nx, ny]);
}
}
}
cnt++;
}
}
let ans = Infinity;
for (let i = 1; i <= islandCnt; i++) {
ans = Math.min(ans, bfs(i));
}
console.log(ans);
✔ 알고리즘 : BFS / DFS
✔ 우선 대륙끼리의 최단경로를 찾기전에 대륙의 구역을 나눠야 한다.
for (let i = 0; i < n; i++) {
for (let j = 0; j < n; j++) {
if (board[i][j] && !visited[i][j]) dfs(i, j, ++islandCnt);
}
}
나눠진 구역은 dfs함수 내에서 board값이 고유한 대륙의번호로 저장된다.
✔ 구역을 나눴으므로 섬끼리 이어주는 다리를 만들어야 한다 (bfs)
✔ bfs에서 탐색 시 경우의 수는 총 3가지이다.
- 첫번째 👉 지도를 벗어나는 경우
if (!check(nx, ny)) continue;
- 두번째 👉 이동하려는 칸이 육지이고, 이동하기 전 대륙의 번호와 다른 번호라면 경로길이 return 후 bfs 종료
if (board[nx][ny] !== 0 && board[nx][ny] !== islandCnt) return cnt;
- 세번째 👉 이동하려는 칸이 바다라면 큐에 넣어주고 계속 진행
if (board[nx][ny] === 0 && !visited[nx][ny]) {
visited[nx][ny] = 1;
queue.push([nx, ny]);
}
✔ 섬의 개수만큼 반복문을 돌며 bfs함수를 실행하여 최소값을 구하면 가장 짧은 다리 하나를 놓아 두 대륙을 연결하는 방법이다.
✔ 난이도 : 백준 기준 골드 3
Author And Source
이 문제에 관하여([백준] 2146 다리 만들기 - javascript), 우리는 이곳에서 더 많은 자료를 발견하고 링크를 클릭하여 보았다 https://velog.io/@ywc8851/백준-2146-다리-만들기-javascript저자 귀속: 원작자 정보가 원작자 URL에 포함되어 있으며 저작권은 원작자 소유입니다.
우수한 개발자 콘텐츠 발견에 전념 (Collection and Share based on the CC Protocol.)