[백준 2589] 보물섬 (Python)

www.acmicpc.net/problem/2589

2589번: 보물섬

 

문제풀이

N, M, board : 입력값

check : 특정 노드 방문 여부

dist : 특정 노드까지의 거리

q : BFS를 위한 deque

 

모든 육지에 대해서 BFS를 통해 갈 수 있는 최대 거리를 구해주면 쉽게 해결할 수 있다.

 

1. 특정 좌표가 육지라면 BFS 시작한다

- 해당 위치에서 상하좌우 중 육지이면서 아직 방문하지 않았다면 방문

 

2. 모든 육지에 대해 1의 과정을 반복한다

 

코드

import sys
from collections import deque

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

def bfs(x, y):
    global ans
    q = deque([(x, y)])
    check = [[False] * M for _ in range(N)]
    dist = [[0] * M for _ in range(N)]
    check[x][y] = True

    while q:
        x, y = q.popleft()
        for k in range(4):
            nx, ny = x + dx[k], y + dy[k]
            if 0 <= nx < N and 0 <= ny < M:
                if not check[nx][ny] and board[nx][ny] == 'L':
                    q.append((nx, ny))
                    dist[nx][ny] = dist[x][y] + 1
                    check[nx][ny] = True
                    ans = max(ans, dist[nx][ny])

if __name__ == '__main__':
    N, M = map(int, sys.stdin.readline().split())
    board = [list(map(str, sys.stdin.readline().rstrip())) for _ in range(N)]
    ans = 0
    for i in range(N):
        for j in range(M):
            if board[i][j] == 'L':
                bfs(i, j)
    print(ans)

 

결과

 

문제풀이나 코드에서 이상한 부분 지적은 언제나 환영합니다!