보물섬 지도를 발견한 후크 선장은 보물을 찾아나섰다. 보물섬 지도는 아래 그림과 같이 직사각형 모양이며 여러 칸으로 나뉘어져 있다. 각 칸은 육지(L)나 바다(W)로 표시되어 있다. 이 지도에서 이동은 상하좌우로 이웃한 육지로만 가능하며, 한 칸 이동하는데 한 시간이 걸린다. 보물은 서로 간에 최단 거리로 이동하는데 있어 가장 긴 시간이 걸리는 육지 두 곳에 나뉘어 묻혀있다. 육지를 나타내는 두 곳 사이를 최단 거리로 이동하려면 같은 곳을 두 번 이상 지나가거나, 멀리 돌아가서는 안 된다.
예를 들어 위와 같이 지도가 주어졌다면 보물은 아래 표시된 두 곳에 묻혀 있게 되고, 이 둘 사이의 최단 거리로 이동하는 시간은 8시간이 된다.
보물 지도가 주어질 때, 보물이 묻혀 있는 두 곳 간의 최단 거리로 이동하는 시간을 구하는 프로그램을 작성하시오.
첫째 줄에는 보물 지도의 세로의 크기와 가로의 크기가 빈칸을 사이에 두고 주어진다. 이어 L과 W로 표시된 보물 지도가 아래의 예와 같이 주어지며, 각 문자 사이에는 빈 칸이 없다. 보물 지도의 가로, 세로의 크기는 각각 50이하이다.
출력
첫째 줄에 보물이 묻혀 있는 두 곳 사이를 최단 거리로 이동하는 시간을 출력한다.
입력 예시
5 7
WLLWWWL
LLLWLLL
LWLWLWW
LWLWLLL
WLLWLWW
출력 예시
8
풀이
핵심은 간단하다. 모든 Land에서 경로 탐색을 시행해 최대 이동 거리를 구하고, 그 중 최댓값을 반환하면 된다. 맵 최대 크기가 50 x 50이므로, O((NM)^2)의 시간복잡도 내에 해결 가능해야 했지만... Python3으로는 시간 초과가 발생한다. 통과되는 코드도 있는 걸로 봐서는, 특수 테스트케이스가 점의 방문 순서 등 사소한 차이에 따라 연산량이 결정되는 것 같다.
시간 초과 이슈 빼고는 별다를 바 없는 문제이므로, 다른 설명은 생략하도록 하겠다.
풀이 코드 (pypy3)
import sys
from collections import deque
input = sys.stdin.readline
dx = [-1, 1, 0, 0]
dy = [0, 0, -1, 1]
def init() :
global N, M
N, M = map(int, input().split())
map_list = [input().strip() for _ in range(N)]
return map_list
def bfs(x, y, map_list) :
global N, M
visited = [[False]*M for _ in range(N)]
q = deque([(x, y, 0)])
visited[y][x] = True
max_dist = 0
while q :
x, y, dist = q.popleft()
max_dist = max(dist, max_dist)
for k in range(4) :
ax, ay = x + dx[k], y + dy[k]
if -1 < ax < M and -1 < ay < N and map_list[ay][ax] == 'L' and not visited[ay][ax] :
visited[ay][ax] = True
q.append((ax, ay, dist+1))
return max_dist
def search(map_list) :
result = 0
for i in range(N) :
for j in range(M) :
if map_list[i][j] == 'L' :
result = max(result, bfs(j, i, map_list))
print(result)
def solve() :
map_list = init()
search(map_list)
solve()
