[ 백준 2589 ] 보물섬 - Python

문제 보기

이 문제는 BFS 문제이다.

 

처음에 문제를 읽으면서 보물의 위치도 따로 구해야 하는지 고민하였다. 보물의 위치를 구하기 위해서 플로이드 알고리즘을 사용하려고 하였으며 보물의 위치를 구하면 거리는 BFS로 간단히 구할 수 있다고 생각했다.

 

하지만 문제를 다시 읽어보니 보물의 위치는 따로 구할 필요가 없었다. 보물의 위치는 두 곳 사이의 거리가 최대인 곳이다. 따라서 2차원 배열에서 육지인 곳을 시작점으로 모두 탐색해보면서 가장 거리가 먼 값을 구하면 된다.

 

• 알고리즘
  • 모든 L값을 시작점으로 하여 다른 L과의 거리를 구한다. (BFS)
  • 위에서 구한 거리와 현재까지 구한 거리를 비교하며 값을 업데이트한다

코드

import sys
from collections import deque

# 상 하 좌 우
dy = [-1, 1, 0, 0]
dx = [0, 0, -1, 1]


def bfs(r, c):
    q = deque([[r, c, 0]])
    visited = {(r, c)}

    while True:
        r, c, cnt = q.popleft()
        for i in range(4):
            new_row, new_col = r + dy[i], c + dx[i]
            if 0 <= new_row < row and 0 <= new_col < col and arr[new_row][new_col] == "L" and (new_row, new_col) not in visited:
                q.append([new_row, new_col, cnt + 1])
                visited.add((new_row, new_col))
        if len(q) == 0:
            return cnt


if __name__ == "__main__":

    # input
    row, col = map(int, sys.stdin.readline().split())
    arr = [list(map(str, sys.stdin.readline().strip())) for _ in range(row)]

    answer = -1
    for i in range(row):
        for j in range(col):
            if arr[i][j] == "L":
                answer = max(answer, bfs(i, j))
    print(answer)