(BOJ)-2589, Python

문제 요약

출처: (BOJ)2589 - 보물섬

$N \times M$ 크기의 지도가 주어진다. 각 칸은 육지($L$) 또는 바다($W$) 로 표시되어 있으며, 이동은 육지에서만 가능하다. 한 칸 이동하는 데 1시간이 걸릴 때, 가장 멀리 떨어진 두 육지(보물이 묻혀 있는 곳) 사이의 최단 이동 시간을 구하는 문제이다.

이동은 상하좌우로 가능하다.
같은 곳을 두 번 이상 지나가거나, 멀리 돌아가서는 안 된다.

접근 과정

1. BFS(큐)

“멀리 돌아가서는 안 된다” 는 조건을 보고, 이전 포스트에서 다룬 것처럼 종점까지의 경로에 돌아가는 루트와 빠른 루트가 있을 경우, 최단 거리를 구하기에는 BFS로 구현하는 것이 더 효율적이라 생각해서 바로 접근했다.

코드 구현

#pypy3 제출
from collections import deque

N, M = map(int, input().split())
graph = [list(map(str, input().rstrip())) for _ in range(N)]

answer = 0
for y in range(N):
    for x in range(M):
        if graph[y][x] != 'L': 
            continue
        visited = [[0 for _ in range(M)] for _ in range(N)]
        dist = [[0 for _ in range(M)] for _ in range(N)]
        
        q = deque()
        q.append([y,x])
        visited[y][x] = 1
        
        while q:
            _y, _x = q.popleft()
                
            for mv_y, mv_x in [[0, -1],[0, 1], [-1, 0],[1, 0]]: 
                dy = _y + mv_y
                dx = _x + mv_x
                if 0 <= dy < N and 0 <= dx < M: 
                    if graph[dy][dx] == 'L': 
                        if visited[dy][dx] == 0: 
                            visited[dy][dx] = 1
                            dist[dy][dx] = dist[_y][_x] + 1
                            q.append([dy,dx]) 
        
        answer = max(answer, max(map(max, dist)))    
print(answer)

회고

python3에서는 시간초과가 났다. 코드를 더 효율적으로 짤 수 있다는 것인데, 논리를 조금 더 세분화해서 짜려고 시도해봐야겠다.