[백준][Python] 2589 보물섬

그래프, bfs / 골드 5

💎

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

2589번: 보물섬

 

 

내 풀이

from collections import deque

def bfs(x, y):
    q = deque()
    q.append((x, y))
    distance = 0

    temp = [[0] * M for _ in range(N)]
    visited = [[False] * M for _ in range(N)]
    visited[x][y] = True

    while q:
        cx, cy = q.popleft()
        
        for k in range(4):
            nx, ny = cx + dx[k], cy + dy[k]
            if 0 <= nx < N and 0 <= ny < M and map[nx][ny] == 'L' and not visited[nx][ny]:
                visited[nx][ny] = True
                distance = temp[cx][cy] + 1
                temp[nx][ny] = distance
                q.append((nx, ny))

    return distance

N, M = map(int, input().split())
map = [[] * M for _ in range(N)]
dx = [-1, 1, 0, 0]
dy = [0, 0, -1, 1]
ans = 0

for i in range(N):
    map[i] = list(input())
    
for i in range(N):
    for j in range(M):
        if map[i][j] == 'L': # 육지 발견
            ans = max(bfs(i, j), ans)

print(ans)

bfs(너비 우선 탐색)로 풀었다.

 

 

코드 설명

 

지도 전체를 돌면서, 육지를 발견할 때마다 bfs를 호출한다.

육지들마다 최단거리로 이동하는 데 가장 긴 시간이 걸리는 육지가 다르기 때문에,

모든 육지를 탐색한 후 최댓값을 알아내야 한다.

for i in range(N):
    for j in range(M):
        if map[i][j] == 'L': # 육지 발견
            ans = max(bfs(i, j), ans)

 

✔️ bfs 함수

 

distance: 현재 육지에서 가장 긴 시간이 걸리는 육지까지 최단거리로 이동하는 시간

temp: 이동 시간을 저장하기 위한 이차원 리스트

visited: 이미 방문한 육지인지 구별하기 위한 이차원 리스트

 

bfs가 불릴 때마다 초기화된다.

distance = 0
temp = [[0] * M for _ in range(N)]
visited = [[False] * M for _ in range(N)]
visited[x][y] = True

 

현재 좌표를 기준으로 상하좌우를 검사한다.

좌표가 범위 내에 있으며 방문하지 않은 육지인 경우,

방문 처리 후, distance에 현재 좌표에서부터 새 좌표까지의 이동 시간을 저장한다.

그 값이 새 좌표의 값이 된다.

deque에 새 좌표를 추가한다.

for k in range(4):
    nx, ny = cx + dx[k], cy + dy[k]
    if 0 <= nx < N and 0 <= ny < M and map[nx][ny] == 'L' and not visited[nx][ny]:
        visited[nx][ny] = True
        distance = temp[cx][cy] + 1
        temp[nx][ny] = distance
        q.append((nx, ny))