문제

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

📝 문제

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

입력

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

출력

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

예제 입력 1

5 7
WLLWWWL
LLLWLLL
LWLWLWW
LWLWLLL
WLLWLWW

예제 출력 1

8

구현

입력받은 maps을 돌면서 해당 위치가 육지인 경우는 bfs로 최단거리를 탐색한다.
첫시도

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

n, m=map(int, input().split())
maps=[list(map(str, input().strip())) for _ in range(n)]

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

def bfs(a, b):
    q=deque()
    q.append([a, b])
    visit=[[0]*m for _ in range(n)]
    visit[a][b]=1
    time=0
    while q:
        x, y=q.popleft()
        for i in range(4):
            nx, ny=x+dx[i], y+dy[i]
            if 0<=nx<n and 0<=ny<m :
                if maps[nx][ny]=='L' and visit[nx][ny]==0:
                    q.append([nx, ny])
                    # 보물은 서로 간에 최단 거리로 이동하는데 있어 가장 긴 시간이 걸리는 육지 두 곳에 있음
                    visit[nx][ny] = visit[x][y] + 1
                    time=max(visit[nx][ny], time)

    return time-1


time=0

for i in range(n) :
    for j in range(m) :
        if(maps[i][j]=='L'):
            time=max(bfs(i, j), time)

print(time)

python은 시간초과가 발생해서 pypy로 제출해서 통과했다.

두번째 시도
보물은 이동하는데 있어서 가장 긴 시간이 걸리는 육지 두곳에 나뉘어 묻혀있다. 그렇기 때문에 maps[i][j]가 다른 두 육지 사이에 있는 경우는 가장 긴 시간이 걸리는 경우가 아니기 때문에 탐색을 할 필요가 없다. 이 부분을 추가해주니까 python으로 제출해도 통과를 했다.

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

n, m=map(int, input().split())
maps=[list(map(str, input().strip())) for _ in range(n)]

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

def bfs(a, b):
    q=deque()
    q.append([a, b])
    visit=[[0]*m for _ in range(n)]
    visit[a][b]=1
    time=0
    while q:
        x, y=q.popleft()
        for i in range(4):
            nx, ny=x+dx[i], y+dy[i]
            if 0<=nx<n and 0<=ny<m :
                if maps[nx][ny]=='L' and visit[nx][ny]==0:
                    q.append([nx, ny])
                    # 보물은 서로 간에 최단 거리로 이동하는데 있어 가장 긴 시간이 걸리는 육지 두 곳에 있음
                    visit[nx][ny] = visit[x][y] + 1
                    time=max(visit[nx][ny], time)

    return time-1


time=0

for i in range(n) :
    for j in range(m) :
        #다른 육지 사이에 있는 경우
        if i>0 and i+1<n :
            if maps[i-1][j]=='L'and maps[i+1][j]=='L':
                continue
        if j>0 and j+1<m :
            if maps[i][j-1]=='L' and maps[i][j+1]=='L':
                continue
        if(maps[i][j]=='L'):
            time=max(bfs(i, j), time)

print(time)