[백준] 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