[BOJ/Python] 2589_보물섬

문제 출처:https://www.acmicpc.net/problem/2589

2589번: 보물섬

 

문제

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

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

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

입력

첫째 줄에는 보물 지도의 세로의 크기와 가로의 크기가 빈칸을 사이에 두고 주어진다. 이어 L과 W로 표시된 보물 지도가 아래의 예와 같이 주어지며, 각 문자 사이에는 빈 칸이 없다. 보물 지도의 가로, 세로의 크기는 각각 50이하이다.

출력

첫째 줄에 보물이 묻혀 있는 두 곳 사이를 최단 거리로 이동하는 시간을 출력한다.

예제 입력 1

5 7
WLLWWWL
LLLWLLL
LWLWLWW
LWLWLLL
WLLWLWW

예제 출력 1

8

 

---

풀이

 

 

연결되어있는 땅(L)들 중 가장 멀리 떨어진 L 사이의 거리를 구하는 문제이다. BFS를 이용하여 문제를 풀이하였고, 모든 땅 L에 대하여 BFS를 수행하게 되면, 시간이 오래 걸리기 때문에 이를 줄이기 위해 다음과 같은 방법을 이용하였다.

• 연결되어있는 땅들이라는 것은 상하좌우 중 하나에 다른 땅이 존재함을 의미한다.
• 이 들 중 가장 멀리 떨어진 두 땅 사이의 거리가 곧 문제에서 요구하는 정답이다.
• 가장 멀리 떨어진 두 땅은 연결되어있는 땅들 내부일 수 없다. (한마디로 바깥쪽에 존재한다.)
• 이를 이용하여 BFS를 수행하기 전에 이 땅이 내부에 존재하는 땅인지 (주위에 다른 땅이 존재하는지) 확인하고, 그렇다면 BFS를 수행하지 않는다.
• 만약 이 땅이 바깥쪽에 존재하는 땅이라면 BFS를 수행한다.

코드는 다음과 같다

 

import sys
import collections
 
dx=[-1,0,1,0]
dy=[0,-1,0,1]
 
h,w = map(int,sys.stdin.readline().split())
grid = []
for _ in range(h):
    grid.append(list(sys.stdin.readline().strip()))
 
def bfs(grid,x,y,visited):
    queue = collections.deque()
    queue.append((x,y))
    visited[x][y]=1
    hour = 0
    count = 1
 
    while queue:
        x,y = queue.popleft()
        count -=1
 
        for i in range(4):
            px = x + dx[i]
            py = y + dy[i]
            if 0<=px<h and 0<=py<w:
                if grid[px][py]=='L' and visited[px][py]==0:
                    visited[px][py]=1
                    queue.append((px,py))
 
        if count==0 and queue:
            hour+=1
            count = len(queue)
    return hour
        
max_hour = 0
for i in range(h):
    for j in range(w):
        if grid[i][j]=='L':
            if 1<=i<h-1 and 1<=j<w-1:
                if grid[i][j-1]=='L' and grid[i][j+1]=='L':
                    continue
                if grid[i+1][j]=='L' or grid[i+1][j]=='L':
                    continue
            visited=[[0] * w for _ in range(h)]
            max_hour = max(max_hour,bfs(grid,i,j,visited))
 
 
print(max_hour)

• 현재 탐색하는 땅 좌우에 다른 땅이 존재하는지, 혹은 상하에 다른 땅이 존재하는지 확인하여 있다면 continue를 이용하여 BFS를 수행하지 않고 넘어간다.
• 만약 존재하지 않는다면 BFS를 수행한다.
• BFS를 이용하여 이동하는 시간 hour를 구하고, 최종적으로 hour의 값이 최대가 되는 경우를 출력한다.