[백준][bfs] 2146 다리 만들기 NodeJs 구현

 

     

목차

 

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

문제

 

 

문제 구현 방향

bfs를 통해 사전 탐색을 하여 각 영역을 표시 해 준 뒤 bfs를 한번 더 해서 최소 거리를 구해 주었다.

 

 

문제 구현 시 주의점

두번째 bfs를 할때 탐색 불가 조건을 철저하게 해주어야 한다.

그렇지 않으면 틀리게 된다.

 

 

코드 구현

const input = require("fs")
  .readFileSync("./dev/stdin", "utf-8")
  .trim()
  .split("\n");

let N = +input[0];

let idx = 1;
let board = [];

while (idx < input.length) {
  let t = input[idx].trim().split(" ").map(Number);
  board.push(t);
  idx++;
}

let dx = [0, 0, 1, -1];
let dy = [1, -1, 0, 0];
let ans = 100000000;
let boardF = Array.from({ length: N }, () => Array(N).fill(0));


function bfs( startX, startY, flag) {
  let queue = [];
  boardF[startY][startX] = flag;
  queue.push([startX, startY]);
  while (queue.length) {
    let [x, y] = queue.shift();
    for (let i = 0; i < 4; i++) {
      let nx = x + dx[i];
      let ny = y + dy[i];
      if (nx < 0 || nx > N - 1 || ny < 0 || ny > N - 1) continue;
      if (boardF[ny][nx] != 0 || !board[ny][nx]) continue;
      queue.push([nx, ny]);
      boardF[ny][nx] = flag;
    }
  }
}

function bfs2(startX, startY) {
  let area = boardF[startY][startX];
  let visit = Array.from({ length: N }, () => Array(N).fill(0));
  let queue = [];

  visit[startY][startX] = 1;
  queue.push([startX, startY]);

  while (queue.length) {
    let [x, y] = queue.shift();
    for (let i = 0; i < 4; i++) {
      let nx = x + dx[i];
      let ny = y + dy[i];
      if (nx < 0 || nx > N - 1 || ny < 0 || ny > N - 1) continue;
      if (visit[ny][nx] || boardF[ny][nx] === area) continue;
      if (boardF[ny][nx] !== 0 && boardF[ny][nx] !== area) {
        ans = Math.min(visit[y][x]-1, ans);
        continue;
      }
      queue.push([nx, ny]);
      visit[ny][nx] = visit[y][x] + 1;
    }
  }
}



let flag = 1;
for (let i = 0; i < N; i++) {
  for (let j = 0; j < N; j++) {
    if (boardF[i][j] === 0 && board[i][j] !== 0) {
      bfs( j, i, flag);
      flag++;
    }
  }
}

for (let i = 0; i < N; i++) {
  for (let j = 0; j < N; j++) {
    if (boardF[i][j] !== 0) {
      bfs2(j, i);
    }
  }
}

console.log(ans);