백준 알고리즘 2589번 보물섬(python)

브루트포스 알고리즘 & BFS 문제이다. 

처음에 지도의 크기가 1이나 2같이 작을 경우를 고려하지 못해서 많이 틀렸다. 

입력을 받을 때 먼저 처리를 해서 -1, 0으로 이루어진 지도를 생성해서 나중에 편하게 처리한다는 점과,

t = max(map(max, a))-1
res = max(res, t)

위 코드와 2줄과 같이 map을 사용해서 보물이 묻혀 있는 두 곳 간의 최단 거리를 간단하게 찾는 부분이

핵심인 것 같다.

from collections import deque
from copy import deepcopy

def bfs(y, x):
    queue = deque()
    queue.append((y, x))
    while queue:
        y, x = queue.popleft()
        for dy, dx in d:
            Y, X = y+dy, x+dx
            if (0 <= Y < N) and (0 <= X < M) and a[Y][X] == 0:
                a[Y][X] = a[y][x] + 1
                queue.append((Y, X))
    
N, M = map(int, input().split())
graph = []
for _ in range(N):
    li = list(input())
    for i in range(M):
        li[i] = 0 if li[i] == 'L' else -1
    graph.append(li)
d = [(-1, 0), (1, 0), (0, -1), (0, 1)]
res = 0
for i in range(N):
    for j in range(M):
        a = deepcopy(graph)
        if a[i][j] == 0:
            a[i][j] = 1
            bfs(i, j)
            t = max(map(max, a))-1
            res = max(res, t)
print(res)