[백준] 2589번 보물선 - 파이썬/BFS

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

from collections import deque

N,M = map(int,input().split())

graph = []

for i in range(N):

    ap_list = list(input())

    graph.append(ap_list)



def bfs(x,y):

    visited = [[0] * M for _ in range(N)]
    distance = [[0] * M for _ in range(N)]

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

    q = deque([(x,y)])
    visited[x][y]=True

    while q:

        cur_x,cur_y = q.popleft()

        for i in range(4):

            nx = cur_x + dx[i]
            ny = cur_y + dy[i]

            if 0<=nx<N and 0<=ny<M and visited[nx][ny]==0 and graph[nx][ny]=='L':
                visited[nx][ny]=True
                q.append((nx,ny))
                distance[nx][ny] = distance[cur_x][cur_y]+1


    return max(map(max,distance)) # distance에서 최대값을 반환


ans = 0

for i in range(N):
    for j in range(M):
        if graph[i][j]=='L':

            check_num = bfs(i,j)

            if check_num>ans:
                ans = check_num

print(ans)

PyPy3으로 제출하였다 (그냥 제출하면 시간초과가 뜬다)

입력한 좌표에서 L로 연결된 최대 거리를 반환하는 함수를 작성하였고

이를 모든 L 좌표에서 반복해서 최대값을 구한다.

이차원 배열의 최댓값을 구하는 코드

max(map(max,distance))

알아두면 좋을 것 같다.