[백준/파이썬] 2589번

📍백준 2589번 문제

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

코드

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

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


def bfs(x, y):
    visited = [[-1] * n for _ in range(m)]
    cnt = 0
    que.append((x, y))
    visited[x][y] = 0
    while que:
        x, y = que.popleft()
        for i in range(4):
            nx = x + dx[i]
            ny = y + dy[i]
            if nx < 0 or nx >= m or ny < 0 or ny >= n:
                continue
            elif visited[nx][ny] == -1 and graph[nx][ny] == 'L':
                visited[nx][ny] = visited[x][y]+1
                cnt = max(cnt, visited[nx][ny])
                que.append((nx, ny))
    return cnt


m, n = map(int, input().split())

graph = []
res = -1
que = deque()

for _ in range(m):
    graph.append(list(input()))
for i in range(m):
    for j in range(n):
        if graph[i][j] == 'L':
            temp = bfs(i, j)
            res = max(res, temp)
print(res)

풀이

모든 육지에서 가장 먼 곳까지의 최단 거리를 구한다.
이후에 res값과 비교에 현재 위치에서 가장 먼 곳까지의 거리가 더 크다면, res에 이 값을 저장해주고, 아니라면 res값은 유지된다.
모든 위치에서 새롭게 BFS를 시작해야하므로 visited도 매번 새로 만들었다.