[BOJ] 2589 보물섬 (node.js)

링크

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

 

문제

보물섬 지도를 발견한 후크 선장은 보물을 찾아나섰다. 보물섬 지도는 아래 그림과 같이 직사각형 모양이며 여러 칸으로 나뉘어져 있다. 각 칸은 육지(L)나 바다(W)로 표시되어 있다. 이 지도에서 이동은 상하좌우로 이웃한 육지로만 가능하며, 한 칸 이동하는데 한 시간이 걸린다. 보물은 서로 간에 최단 거리로 이동하는데 있어 가장 긴 시간이 걸리는 육지 두 곳에 나뉘어 묻혀있다. 육지를 나타내는 두 곳 사이를 최단 거리로 이동하려면 같은 곳을 두 번 이상 지나가거나, 멀리 돌아가서는 안 된다.

 

예를 들어 위와 같이 지도가 주어졌다면 보물은 아래 표시된 두 곳에 묻혀 있게 되고, 이 둘 사이의 최단 거리로 이동하는 시간은 8시간이 된다.

 

 

보물 지도가 주어질 때, 보물이 묻혀 있는 두 곳 간의 최단 거리로 이동하는 시간을 구하는 프로그램을 작성하시오.

 

풀이 과정

접근법 : bfs

구해야하는 값은 보물이 묻혀있는 곳의 거리를 구하는 것이고,

이 거리는 서로간에 최단 거리로 이동하는데 있어 가장 긴 시간이 걸리는 육지 2곳에 나눠 묻혀져 있다.

 

즉, 서로간에 최단 거리로 이동할 때 가장 긴 시간이 걸리는 육지 2곳을 찾을 때, 그 거리를 구하면 되는 것이다.

 

직관적으로 모든 땅에서 시작하여 다른 땅까지 가는 거리를 재보면 된다는 것을 알 수 있다.

그렇다면 탐색의 시작점을 정해야 하는데,

전체 보물 지도의 가로, 세로 길이는 최대 50이므로 모든 지점을 시작점으로 한다고 해도 2500x50x50 = 625,000회의 연산이 수행되기 때문에 전체 지점을 시작점으로 하는 풀이가 가능하다.

 

2중 for문을 통해 해당 지점이 땅일 때만 계산했고, 두 곳간의 최단 거리를 구하는 문제이기 때문에 bfs 알고리즘을 사용해서 풀이했다.

 

 

코드

const filePath = process.platform === "linux" ? "/dev/stdin" : "./input.txt";
const input = require("fs").readFileSync(filePath).toString().trim().split("\n");

const [R, C] = input[0].split(" ").map(Number);
const map = input.slice(1).map((x) => x.split(""));

const dx = [0, 0, -1, 1];
const dy = [-1, 1, 0, 0];

const bfs = (x, y) => {
  const visited = Array.from({ length: R }, () => Array(C).fill(false));
  visited[x][y] = true;

  let maxDepth = 0;
  const queue = [[x, y, 0]];

  while (queue.length > 0) {
    const [cx, cy, depth] = queue.shift();

    maxDepth = Math.max(depth, maxDepth);

    for (let i = 0; i < 4; i++) {
      const nx = cx + dx[i];
      const ny = cy + dy[i];

      if (nx < 0 || nx >= R || ny < 0 || ny >= C) continue;
      if (visited[nx][ny] || map[nx][ny] === "W") continue;

      visited[nx][ny] = true;
      queue.push([nx, ny, depth + 1]);
    }
  }

  return maxDepth;
};

let answer = 0;

for (let i = 0; i < R; i++) {
  for (let j = 0; j < C; j++) {
    if (map[i][j] === "W") continue;
    answer = Math.max(answer, bfs(i, j));
  }
}

console.log(answer);