[boj] 백준 2589 보물섬 python 풀이

문제

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

2589번: 보물섬

 

문제 풀이

bfs 문제로, 모든 땅에 대해서 가장 거리가 먼 육지를 bfs로 찾고 최대값을 갱신해가면서 완전탐색 돌리면 된다. 효율적인지는 모르겠음..

 

코드

import sys
input = sys.stdin.readline
import collections

H, W = map(int,input().split())
MAP = [list(input().strip()) for _ in range(H)]
MAX = 0

def bfs(MAP, i , j):
    move = {(-1,0), (0,1), (0,-1), (1,0)}
    visited = [[0 for _ in range(W)] for _ in range(H)]

    q = collections.deque()
    q.append((i,j,0))
    visited[i][j] = 1

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

        for tx, ty in move:
            nx = x + tx
            ny = y + ty

            if 0<=nx<H and 0<=ny<W and visited[nx][ny] == 0 and MAP[nx][ny] == 'L':
                q.append((nx,ny,cnt+1))
                visited[nx][ny] = 1

    return cnt
    
for i in range(H):
    for j in range(W):
        if MAP[i][j] == 'L': # 가장 멀리 떨어진 곳 탐색 시작
            MAX = max(MAX,bfs(MAP, i, j))

print(MAX)