(Python) - BOJ(2589번) : 보물섬

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

2589번: 보물섬

---

• 해설 : 

보물섬 지도를 발견한 후크 선장은 보물을 찾아나섰다. 보물섬 지도는 아래 그림과 같이 직사각형 모양이며 여러 칸으로 나뉘어져 있다. 각 칸은 육지(L)나 바다(W)로 표시되어 있다. 이 지도에서 이동은 상하좌우로 이웃한 육지로만 가능하며, 한 칸 이동하는데 한 시간이 걸린다. 보물은 서로 간에 최단 거리로 이동하는데 있어 가장 긴 시간이 걸리는 육지 두 곳에 나뉘어 묻혀있다. 육지를 나타내는 두 곳 사이를 최단 거리로 이동하려면 같은 곳을 두 번 이상 지나가거나, 멀리 돌아가서는 안 된다.

예를 들어 위와 같이 지도가 주어졌다면 보물은 아래 표시된 두 곳에 묻혀 있게 되고, 이 둘 사이의 최단 거리로 이동하는 시간은 8시간이 된다.

보물 지도가 주어질 때, 보물이 묻혀 있는 두 곳 간의 최단 거리로 이동하는 시간을 구하는 프로그램을 작성하시오.

 

 

 

---

• 풀이 :

육지를 만날 때마다 bfs로 탐색한다. 

이 때, 보물이 있을 수 있는 위치 (max값)을 갱신하여 보물 사이의 최단거리를 계산하면 된다.

 

 

---

• 소스코드 : 

 

import sys
from collections import deque
dx = [-1,1,0,0]
dy = [0,0,-1,1]
 
def bfs(start):
    queue = deque([start])
    cnt = [[-1]*m for _ in range(n)]
    ma = 0
    cnt[start[0]][start[1]] = 0
    while queue:
        x,y = queue.popleft()
        for k in range(4):
            ax = x + dx[k]
            ay = y + dy[k]
            if 0 <= ax < n and 0 <= ay < m:
                if cnt[ax][ay] == -1 and maze[ax][ay] == "L":
                    queue.append([ax,ay])
                    cnt[ax][ay] = cnt[x][y]+1
                    ma = max(ma, cnt[ax][ay])
 
    return ma
 
if __name__ == "__main__":
    n,m = map(int,sys.stdin.readline().split())
    maze = [list(input()) for _ in range(n)]
    answer = 0
    for i in range(n):
        for j in range(m):
            if maze[i][j] == "L":
                answer = max(answer,bfs([i,j]))
    print(answer)