[백준 2589번] 보물섬 - PyPy3

문제

2589번: 보물섬

 

예전에 푼 문제인데 오랜만에 다시 푸니 이틀 정도 애먹었다..
python으로 제출시 시간 초과가 나서 PyPy3로 제출.

---

풀이

# 2589번 보물섬

# 육지 L, 바다 W

# 상하좌우 육지 이동 가능, 한 칸 이동시 한 시간

# 보물 -> 서로 간에 최단 거리로 이동(BFS)하는데 있어 가장 긴 시간이 걸리는 육지 두 곳에 나뉘어 묻혀있음.
# -> 끝에서 끝으로 이동시 서로 가장 긴 시간이 걸리는 육지에서 최단거리를 구해라! (완전 탐색)

# 보물이 묻혀 있는 두 곳 간의 최단 거리!!로 이동하는 시간을 구하는 프로그램을 작성하시오.

# bfs
from collections import deque
import sys
input = sys.stdin.readline

# 보물 지도의 세로 크기, 가로 크기
y_size, x_size = map(int, input().split())

x_map = [list(input().rstrip()) for _ in range(y_size)]

# 상, 하, 좌, 우
dy = [-1, 1, 0, 0]
dx = [0, 0, -1, 1]

max_distance = 0

for i in range(y_size):
    for j in range(x_size):
        if x_map[i][j] == 'L':
            visited = [[0 for _ in range(x_size)] for _ in range(y_size)] # 방문 기록
            dist = [[0 for _ in range(x_size)] for _ in range(y_size)] # 거리 기록
            queue = deque()
            queue.append([i, j])
            visited[i][j] = 1

            while queue:
                y, x = queue.popleft()

                for k in range(4):
                    ny = y + dy[k]
                    nx = x + dx[k]
                    if 0 <= ny < y_size and 0 <= nx < x_size: # 지도 범위를 넘어가지 않고
                        if x_map[ny][nx] == 'L' and visited[ny][nx] == 0: # 육지이고 방문하지 않았다면
                            queue.append([ny, nx])
                            visited[ny][nx] = 1
                            dist[ny][nx] = dist[y][x] + 1
                            max_distance = max(max_distance, dist[ny][nx])

print(max_distance)

 

아이디어

• 육지를 나타내는 두 곳 사이를 최단 거리로 이동하려면 주변을 다 가는 DFS가 아니라 BFS로 풀어야 최단 거리를 구할 수 있다.
• 완전 탐색으로 모든 육지 지점을 방문하여 각 지점까지의 거리를 dist에 기록 후, 어떤 육지 지점으로부터 다른 육지 지점까지의 거리가 현재까지 발견된 최대 거리보다 긴 경우 max_distance을 업데이트한다.
  
  for 문 안 i, j, k 변수명 다르게 하기

시간 복잡도

- 각 육지 지점마다 BFS를 실행하므로 O(V(정점의 수_육지 지점) + E(간선의 수_육지 간 이동 가능 경로))이다.
-> 최악의 경우 모든 지점이 육지이므로 V = N x M, BFS는 각 정점에 대해 상하좌우 네 방향을 확인하므로, E는 4V

-> 전체 시간복잡도 = O(NM * NM) = O(N**2M**2) 

공간 복잡도

- 지도를 저장하는데 O(NM)의 공간이 필요. visited, dist 배열을 저장하는데도 각각 O(NM)의 공간이 필요

-> 전체 공간 복잡도 O(NM)