[백준 - Python] 2589. 보물섬 (완전 탐색)

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

2589번: 보물섬

 

코드

from collections import deque
import sys
input = sys.stdin.readline

n, m = map(int, input().split())
treasureMap = [[] for _ in range(n)]
for i in range(n):
    row = input()
    for r in row:
        treasureMap[i].append(r)

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

def bfs(i, j):
    queue = deque()
    queue.append((i, j))
    visited = [[0] * m for _ in range(n)]
    visited[i][j] = 1
    cnt = 0   # 이동한 거리 카운트

    while queue:
        x, y = queue.popleft()
        for i in range(4):
            nx = x + dx[i]
            ny = y + dy[i]
            if 0 <= nx < n and 0 <= ny < m:
                if treasureMap[nx][ny] == 'L' and visited[nx][ny] == 0:
                    visited[nx][ny] = visited[x][y] + 1
                    cnt = max(cnt, visited[nx][ny])
                    queue.append((nx, ny))
    return cnt - 1


cnt = 0
for i in range(n):
    for j in range(m):
        if treasureMap[i][j] == 'L':
            cnt = max(cnt, bfs(i, j))

print(cnt)

 

보물섬 지도가 주어지는데

지도는 직사각형 모양이고 여러 칸으로 나누어져 있다.

각 칸은 육지 L  혹은 바다 W로 표시 되어 있다.

한 칸 이동하는데 한 시간이 걸리고,

보물은 서로 간에 최단 거리로 이동하는데 있어 가장 긴 시간이 걸리는 육지 두 곳에 나뉘어 묻혀 있다고 한다.

 

우선, 보물섬에서 육지인 부분부터 탐색을 시작할 수 있도록

이중 반복문을 활용해 L로 표시된 지점을 찾고

해당 부분부터 BFS를 실행시킨다.

 

BFS 함수를 확인해보자.

deque라이브러리를 활용해 큐를 생성해주고

시작 좌표를 넣어준다.

해당 시작 좌표를 시작으로 방문한 지점들의 방문 여부를 저장할 visited 변수를 선언해주고

시작 노드를 방문 처리 해준다.

그리고 이동한 거리를 카운팅 해줄 cnt 변수를 선언해준다

 

큐가 빌 때까지 반복문을 돌며

상하좌우 네 방향을 확인하는데

방향의 좌표가 보물섬 내 범위에 해당하고

육지이면서 아직 방문하지 않은 노드인 경우에

방문 처리를 해준다

 

여기서 유의해서 봐야 하는 것은

방문 처리 여부를 저장하는 변수를

이동한 거리를 저장하는 변수로도 사용했다는 것이다

 

cnt = max(cnt, visited[nx][ny])

 

위의 코드를 눈여겨 봐야 한다.

현재 저장된 이동거리와

새로 방문한 지점까지의 이동거리를 비교해 최댓값으로 갱신해주는 코드이다

 

다른 문제에서도 유용하게 쓰이니 꼭 기억해두자 !

 

방문 처리 및 이동한 거리를 저장하고

최댓값을 갱신해 준 다음에는

큐에 해당 좌표를 넣어준다

 

반복문을 탈출했을 시에,

cnt에 저장되어 있는 값은 지나온 전체 육지의 칸 개수이다

구해야 하는 것은 최소 이동 시간이므로 cnt - 1 값을 반환한다

 

bfs 하나마다 반환되는 cnt 값은

이어져 있는 육지 하나에 대한 이동거리 최댓값이므로

각 육지 덩어리마다 bfs를 돌려주고 최종 최댓값을 cnt에 담아 반환해준다

해당 부분에서도 위에서 언급한 비교 후 최댓값으로 갱신해주는 코드를 사용했다

 

해당 코드는 python3로는 시간 초과가 나고,

pypy3로는 통과가 되었다.

 

 

참고 자료

https://emhaki.tistory.com/entry/python%EB%B0%B1%EC%A4%80-2589%EB%B2%88-%EB%B3%B4%EB%AC%BC%EC%84%ACBFS