백준 2589번 : 보물섬 in Python

2589번: 보물섬

 

www.acmicpc.net

이 문제는 보물 지도가 주어질 때 보물이 묻혀 있는 두 곳 간의 최단 거리로 이동하는 시간을 구하는 문제이다. 단, 보물은 서로 간에 최단 거리로 이동하는데 있어 가장 긴 시간이 걸리는 육지 두 곳에 나뉘어 묻혀있다.

우선, 보물의 위치를 알기 위해서, 그리고 보물 간의 최단 거리를 구하기 위해서는 결국 지도 내 두 지점 사이의 최단 거리를 구해야 한다. 그러므로 이 문제는 그래프 탐색 중 너비 우선 탐색을 이용해야 한다. 만약 보물의 위치만 알 수 있다면 이를 너비 우선 탐색을 이용해 최단 거리를 쉽게 구할 수 있을 것이다.

그렇다면 보물의 위치는 어떻게 구할 수 있을까? 보물은 최단 거리로 이동하는데 있어 가장 긴 시간이 걸리는 육지 두 곳에 나뉘어 묻혀있다. 그러므로 생각할 수 있는 방법은 지도 상의 모든 육지에 대해 너비 우선 탐색을 시행하고 그 육지와 최단 거리 상으로 가장 멀리 떨어져 있는 육지까지의 최단 거리를 각각 구한 뒤, 그 최단 거리들 중 가장 큰 값이 되는 경우를 찾으면 될 것이다. 물론 이는 같은 경로를 여러 번 탐색한다는 점에서 비효율적인 알고리즘이지만, 이 문제의 입력이 크진 않아서 문제 해결에는 큰 문제가 없다.

이를 코드로 구현하면 다음과 같다.

from collections import deque
N, M = map(int, input().split())
m = []
for _ in range(N):
    m.append(list(input()))
# 너비 우선 탐색을 수행하고, 인자로 주어진 시작점에서 
# 가장 멀리 떨어진 지점까지의 최단 거리를 반환하는 함수
def BFS(i, j):
    global N, M
    queue = deque()
    queue.append([i, j])
    visited[i][j] = True
    # 시작점으로부터 가장 멀리 떨어진 지점까지의 최단 거리를 저장하는 변수
    res = 0
    d = [[0]*M for _ in range(N)]
    dx = [-1, 1, 0, 0]
    dy = [0, 0, -1, 1]
    while queue:
        x, y = queue.popleft()
        for i in range(4):
            next_x = x + dx[i]
            next_y = y + dy[i]
            if 0<=next_x<N and 0<=next_y<M and m[next_x][next_y] == 'L' and not visited[next_x][next_y]:
                visited[next_x][next_y] = True
                d[next_x][next_y] = d[x][y] + 1
                queue.append([next_x, next_y])
                # 가장 멀리 떨어진 지점까지의 최단 거리를 갱신한다.
                if res < d[next_x][next_y]:
                    res = d[next_x][next_y]
    return res
res = 0
for i in range(N):
    for j in range(M):
        if m[i][j] == 'L':
            visited = [[False]*M for _ in range(N)]
            res = max(res, BFS(i, j))
print(res)