[백준/Python] 2589번: 보물섬

문제

https://www.acmicpc.net/problem/2589

2589번: 보물섬

---

문제 요약

각 칸이 육지(L), 바다(W)로 이루어진 2차원 배열 보물 지도가 있다.

 

보물은 서로 간에 최단 거리로 이동하는데 있어 가장 긴 시간이 걸리는 육지 두 곳에 나뉘어 묻혀 있다.

+ 최단 거리로 이동하려면 같은 곳을 두 번 이상 지나가거나 멀리 돌아가서는 안된다.

 

보물이 묻혀 있는 두 곳 간의 최단 거리로 이동하는 시간을 출력한다.

+ 한 칸을 이동하는 데 1이 걸린다.

---

코드

from collections import deque

def bfs(i, j):
    global res, height, width
    
    check = [[0] * width for _ in range(height)]
    que = deque()
    que.append([i, j])    
    check[i][j] = 1
    
    while que:
        x, y = que.popleft()

        for d in range(4):
            nx = x + dx[d]
            ny = y + dy[d]
            if 0 <= nx and 0 <= ny and nx < height and ny < width and check[nx][ny] == 0 and board[nx][ny] == 'L':
                que.append([nx, ny])
                check[nx][ny] = check[x][y] + 1
                res = max(res, check[nx][ny])

height, width = map(int, input().split())

board = [list(input()) for _ in range(height)]

res = 0

dx = [0, 0, 1, -1]
dy = [1, -1, 0, 0]

for i in range(height):
    for j in range(width):
        if board[i][j] == 'L':
            bfs(i, j)
            
print(res - 1)

---

코드 설명

모든 육지 인덱스에서 보물이 묻혀 있다 가정하고, 큐를 이용하여 넓이 우선 탐색 (BFS) 을 진행한다.

=> 해당 인덱스부터 최단 경로의 가장 멀리 있는 인덱스까지의 거리를 계산하고 res를 갱신한다.

 

최단 경로의 가장 멀리 있는 인덱스까지의 거리 = 보물이 묻혀 있는 다른 한 곳까지의 거리

 

+ Python으로 제출 시 시간 초과 문제가 발생하므로, PyPy3로 제출해야한다.