백준 2589 - 보물섬

문제

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

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

접근법

일단 최단 이라는 단어랑 가장 긴 시간이라는 단어가 같이 있어서 좀 헷갈릴 수 있는데, 돌아가지 말고 제대로 갔을 때 가장 긴 시간이 걸리는 두 육지에 보물이 있고, 보물 육지 사이의 거리를 구하라는 소리는 위에서 구한 가장 긴 시간과 똑같음

일단 땅과 땅 사이만 이동 가능 + 상하좌우로만 이동 가능하다는 점에서 dfs를 사용해서 각 땅에서 갈 수 있는 최대의 땅과 그때까지 걸리는 시간을 구해서, 가장 큰 값이 정답이 됨

풀이

일단 주어진 좌표에서 땅인 곳이 있으면 그 지점에서 시작 - dfs를 이용해서 최대로 갈 수 있는 지점을 찾는다

사실 여기까지는 어렵지 않은데, 그럼 최대로 갈 수 있는 지점까지 걸린 시간을 구하는 게 좀 어려웠긴한데 약간 기출유형이 있어서 그거 생각해서 품
ex)
[0][1]이 L이기 때문에 이 지점에서 dfs를 돌리면 다음 갈 수 있는 지점은 [0][2] , [1][1]이 나옴

• 생각해보면 이 두 지점은 시작점인 [0][1]에서부터 한시간(첫번째)뒤 이동할 수 있는 지점이 됨
  [0][2]에서 이동 가능한 [1][2]는 [0][2]에서는 한시간 뒤 이동할 수 있는 지점, [0][1]에서는 두시간 뒤 이동할 수 있는 지점이 됨
• 한마디로 다음 지점의 값 = 시작점 + 1을 하게 되면 n시간 뒤 이동한 위치를 알 수 있고, dfs가 끝나면 이 값들 중 가장 큰 값이 최대 지점까지 이동했을 때 걸린 시간이 됨
• 콘솔 찍어보면 느낌 옴

코드

const fs = require("fs");
let input = fs
  .readFileSync("./test.txt")
  .toString()
  .trim()
  .split("\n")
  .map((v) => v.split(" "));
const [n, m] = input.shift().map((v) => Number(v));
const map = input.map((v) => v[0].split(""));
const dirs = [
  [0, 1],
  [0, -1],
  [1, 0],
  [-1, 0],
];
//map에서 L인 부분이 발견되면, L을 dfs돌려서 갈 수 있는 최대의 값의 좌표를 찾기
const makeArr = () => {
  return Array(n)
    .fill(0)
    .map((v) => Array(m).fill(0));
};

const dfs = (cord) => {
  const visited = makeArr();
  visited[cord[0]][cord[1]] = 1;
  const queue = [cord];
  while (queue.length) {
    let [x, y] = queue.shift();
    for (let dir of dirs) {
      const [nextX, nextY] = [x + dir[0], y + dir[1]];
      if (nextX < 0 || nextX >= n || nextY < 0 || nextY >= m) {
        continue;
      }
      if (map[nextX][nextY] === "L" && !visited[nextX][nextY]) {
        queue.push([nextX, nextY]);
        visited[nextX][nextY] = visited[x][y] + 1;
        //이 부분을 통해서 이동할 수 있는 최대치의 땅과 그 땅까지 이동한 시간을 알 수 있음
      }
    }
  }
  return Math.max(...visited.flat());
};
let result = 0;
for (let i = 0; i < n; i++) {
  for (let j = 0; j < m; j++) {
    if (map[i][j] === "L") {
      result = Math.max(result, dfs([i, j]));
    }
  }
}
console.log(result - 1);