[백준/Python] 2589 보물섬

문제 링크

2589번: 보물섬

 

문제 풀이

• 이 문제는 각 육지에서 다른 육지로의 거리 중 최대 거리를 구하는 문제이다.
• 먼저, 육지(L)인 경우, 너비 우선 탐색을 진행할 수 있도록 한다(for문). 너비 우선 탐색을 진행한 후에는 결과값(res)을 기존의 값과 비교하여 더 큰 값을 저장하도록 한다.
• 너비 우선 탐색을 진행할 때에는 현재 육지에서 다른 육지와의 거리를 구할 수 있도록 카운트값(c)를 같이 큐에 넣어 진행한다. 큐가 빌 때까지 진행하는데, 마지막에 들어간 값이 가장 거리가 먼 육지가 되므로 최종적으로는 카운트값을 반환해야 한다.
• 모든 육지에 대해서 너비 우선 탐색을 진행하면, 최대 거리를 구할 수 있다.

 

전체 코드

import sys
from collections import deque

def bfs(x, y, c):
    queue = deque()
    queue.append((x, y, c))
    visited[x][y] = True
    while queue:
        x, y, c = queue.popleft()
        for i in range(4):
            nx = x + dx[i]
            ny = y + dy[i]
            if nx < 0 or nx >= n or ny < 0 or ny >= m:
                continue
            if not visited[nx][ny] and arr[nx][ny] == "L":
                visited[nx][ny] = True
                queue.append((nx, ny, c+1))
    return c

n, m = map(int, sys.stdin.readline().split())
arr = [list(sys.stdin.readline().strip()) for _ in range(n)]

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

res = 0
for i in range(n):
    for j in range(m):
        if arr[i][j] == "L":
            visited = [[False] * m for _ in range(n)]
            res = max(res, bfs(i, j, 0))

print(res)