[백준] 2589. 보물섬 풀이 (Python, TypeScript)

2589번: 보물섬

접근한 방법

비교적 풀이법이 단순한 완전탐색 문제. 지도가 몇 개의 육지로 나뉘어져 있는 지는 아무 상관 없습니다. L에 해당하는 모든 칸을 확인하여 BFS를 수행합니다.

 

1. L이면 BFS를 들어갑니다.

2. 시작점을 1로 잡고 이후 상하좌우로 방문하는 L칸 마다 +1씩 더하여 값을 넣어줍니다. (방문 처리)

3. 마지막으로 방문한 칸에서 시작점인 1을 뺀 값이 해당 좌표에서 계산된 시작점에서 가장 먼 지점까지의 거리가 됩니다.

4. 모든 L칸에 대해서 1~3 과정을 수행 후 나온 BFS결괏값 중 최댓값이 정답이 됩니다.

 

왜 최댓값이 정답이 되느냐?

주변 우선 탐색의 특성상 절대로 경로를 틀어 돌아가는 일이 없습니다. 그러므로 어떤 지점에서 탐색을 해도 최단 거리가 됩니다. 단, 문제에서 보물의 위치는 "서로 간에 최단 거리로 이동하는데 있어 가장 긴 시간이 걸리는 육지 두 곳에 나뉘어 묻혀있다" 라고 되어 있기 때문에 모든 계산된 거리들 중 최댓값이 되었을 때의 위치가 두 보물의 위치일 수 밖에 없습니다.

 

Python

import sys
input = sys.stdin.readline

n, m = map(int, input().split())
arr = [input().rstrip() for _ in range(n)]
dist = ((-1, 0), (1, 0), (0, -1), (0, 1))
import collections
def bfs(sr, sc):
    q = collections.deque()
    q.append((sr, sc, 0))
    times = [[0] * m for _ in range(n)]
    times[sr][sc] = 1
    t = 0
    while q:
        qr, qc, cnt = q.popleft()
        t = cnt + 1
        for d in dist:
            dr, dc = qr + d[0], qc + d[1]
            if dr < 0 or dc < 0 or dr >= n or dc >= m:
                continue
            if arr[dr][dc] == "L" and times[dr][dc] == 0:
                times[dr][dc] = cnt + 1
                q.append((dr, dc, cnt + 1))
    return t - 1
result = 0
for i in range(n):
    for j in range(m):
        if arr[i][j] == "L":
            result = max(result, bfs(i, j))
print(result)

TypeScript

function sol2589(n: number, m: number, arr: Array<string>) {
  const dist = [
    [-1, 0],
    [1, 0],
    [0, -1],
    [0, 1],
  ];
  const bfs = (sr: number, sc: number) => {
    const q: Array<[number, number, number]> = [];
    let front = 0;
    q.push([sr, sc, 0]);
    const times = Array.from({ length: n }, () => Array(m).fill(0));
    times[sr][sc] = 1;
    let t = 0;
    while (q[front]) {
      const [qr, qc, cnt] = q[front++];
      t = cnt + 1;
      for (const d of dist) {
        const [dr, dc]: [number, number] = [qr + d[0], qc + d[1]];
        if (dr < 0 || dc < 0 || dr >= n || dc >= m) continue;
        if (arr[dr][dc] === "L" && times[dr][dc] === 0) {
          times[dr][dc] = cnt + 1;
          q.push([dr, dc, cnt + 1]);
        }
      }
    }
    return t - 1;
  };
  let result = 0;
  for (let i = 0; i < n; i += 1) {
    for (let j = 0; j < m; j += 1) {
      if (arr[i][j] === "L") result = Math.max(result, bfs(i, j));
    }
  }
  return result;
}
console.log(
  sol2589(5, 7, ["WLLWWWL", "LLLWLLL", "LWLWLWW", "LWLWLLL", "WLLWLWW"])
);