보물섬

풀이

 문제 유형은 BFS, 최단 거리, 완전 탐색으로 그래프에서 L의 위치마다 BFS를 돌린다. BFS에서는 L에서부터의 거리 중 최댓값을 반환하면 된다. 아래와 같이 코드를 짜고 제출했지만 Python3로는 시간초과 판정이 뜨고 PyPy3로는 통과다.

from collections import deque
import sys

h, w = map(int, input().split())
graph = []
for i in range(h):
    graph.append(list(sys.stdin.readline()))

# 동, 서, 남, 북
dx = [0,0,1,-1]
dy = [1,-1,0,0]

def bfs(x,y):
    visited = [[-1] * w for _ in range(h)]
    queue = deque([(x,y,0)])
    visited[x][y] = 0
    while queue:
        x,y,c = queue.popleft()
        for i in range(4):
            nx = x + dx[i]
            ny = y + dy[i]
            if 0<=nx<h and 0<=ny<w:
                if graph[nx][ny] == 'L' and visited[nx][ny] == -1:
                    visited[nx][ny] = c+1
                    queue.append((nx,ny,c+1))
    return c

result = 0
for x in range(h):
    for y in range(w):
        if graph[x][y] == 'L':
            if result < bfs(x,y):
                result = bfs(x,y)
print(result)

Python3로 통과하려면 이중 for문에서 L인 부분을 탐색할 때 상하 혹은 좌우에 L이 동시에 존재한다면 그곳은 가장자리가 아니기 때문에 탐색을 넘겨야 한다. 아래 부분만 수정해주면 된다.

for x in range(h):
    for y in range(w):
        if 0<x<h-1:
            if graph[x-1][y] == 'L' and graph[x+1][y] == 'L':
                continue
        if 0<y<w-1:
            if graph[x][y-1] == 'L' and graph[x][y+1] =='L':
                continue
        if graph[x][y] == 'L':
            if result < bfs(x,y):
                result = bfs(x,y)
print(result)

시간복잡도 : O((hw)^2)