[Python/파이썬] 백준 2589 - 보물섬

문제 설명

 

입출력 예제

---

풀이 코드

처음에 육지중에 땅의 크기가 가장 큰 섬를 bfs로 구한다음에 가장 큰 섬에서 또 bfs로 보물 사이의 최단거리를 구해야하나? 라고 생각했다.

 하지만 그럴 필요 없이 두 섬에서 보물 사이의 거리가 가장 먼 값을 구하면 된다. 

 

정답 코드

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

r, c = map(int, input().split())
board = [list(input().rstrip()) for _ in range(r)]

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

def bfs(x, y):
    q = deque()
    q.append((x, y))
    visited = [[-1] * c for _ in range(r)]
    visited[x][y] = 0
    cnt = 0

    while q:
        x, y = q.popleft()

        for i in range(4):
            nx = x + dx[i]
            ny = y + dy[i]

            if 0 <= nx < r and 0 <= ny < c and visited[nx][ny] == -1:
                if board[nx][ny] == "L":
                    q.append((nx, ny))
                    visited[nx][ny] = visited[x][y] + 1
                    cnt = max(cnt, visited[nx][ny])
    return cnt

result = 0
for x in range(r):
    for y in range(c):
        if board[x][y] == "L":
            result = max(result, bfs(x, y))

print(result)