[Python] 백준 2589번 - 보물섬

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

2589번: 보물섬

 

bfs 풀 때 visited 배열 안 쓰고 푸는 게 편하길래 이 문제도 그렇게 접근했는데 잘 안 풀려서 결국 visited 배열을 사용하였다.

모든 L에 대해서 bfs 탐색을 시도해야 해서 시간초과 날까봐 코드 짤 때부터 걱정했는데 역시나였다.

pypy3로 제출해서 성공하였다.

 

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

def bfs(y, x):
    q = deque()
    visited = [[0 for _ in range(m)] for _ in range(n)]
    visited[y][x] = 1
    q.append((y, x))
    time = 0
    while q:
        y, x = q.popleft()
        dxdy = [(-1, 0), (1, 0), (0, -1), (0, 1)]
        for dy, dx in dxdy:
            nx = x + dx
            ny = y + dy
            if -1 < nx < m and -1 < ny < n:
                if tsmap[ny][nx] == 'L' and visited[ny][nx] == 0:
                    visited[ny][nx] = visited[y][x] + 1
                    q.append((ny, nx))
                    time = max(time, visited[ny][nx])
    return time - 1
    
n, m = map(int, input().split()) #n: 세로(y), m: 가로(x)
tsmap = []
ans = 0
for _ in range(n):
    tsmap.append(list(map(str, input().strip())))

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

print(ans)