백준 2146번 : 다리 만들기 in Python

2146번: 다리 만들기

 

www.acmicpc.net

이 문제는 여러 섬으로 이루어진 나라에서 한 섬과 다른 섬을 잇는 다리 중 가장 짧은 것의 길이를 구하는 문제이다.

이 문제를 해결하기 위해서는 각 섬의 위치를 파악하고, 임의의 서로 다른 두 섬 사이의 최단 거리를 구해야 한다.

먼저 각 섬의 위치를 파악하기 위해서는, 지도 내 모든 좌표를 순회하면서 해당 좌표가 육지인 경우 그 지점을 시작으로 그래프 탐색을 시행해야 한다. 단, 이때는 섬의 위치를 파악하기 위해 그래프를 탐색하고 있으므로 이웃한 지점 중 육지인 지점만 탐색한다. 그리고 각 지점이 어떤 섬에 속하는지를 저장해야 한다. 이를 위해 각 섬에 부여할 숫자를 저장하는 변수 cnt를 만들고, 지도 내 좌표를 순회하는 중 방문하지 않은 지점을 찾았다는 것은 새로운 섬을 발견했다는 것을 의미하므로 cnt를 1 증가시킨 뒤 해당 섬을 탐색하면서 그 섬에 속한 좌표들에 cnt 값을 부여한다.

이를 완료하면 각 섬마다 섬 내의 모든 좌표에 해당 섬이 부여받은 cnt 값이 저장된다. 이번에는 임의의 서로 다른 두 섬 사이의 최단 거리를 구해야 한다. 이를 위해 위의 너비 우선 탐색 방식을 약간 바꾼다. 이제는 육지가 아닌 바다를 건너야 하므로 그래프 탐색 시 이웃한 지점 중 바다인 지점만 탐색하고, 최단 거리를 구해야 하므로 이를 따로 저장해둬야 한다. 특히 그래프 탐색 중 출발한 섬과 다른 섬을 만난 경우에는 해당 섬에서 가장 가까운 섬과의 거리를 구한 것이므로 이를 반환한다.

이렇게 구현한 너비 우선 탐색을 지도 내 모든 육지 좌표에 대해 수행한 뒤 반환된 결과값 중 가장 작은 값을 출력하면 된다.

이를 코드로 구현하면 다음과 같다.

from collections import deque
import sys
N = int(input())
m = []
for _ in range(N):
    m.append(list(map(int, input().split())))
dx = [-1, 1, 0, 0]
dy = [0, 0, -1, 1]
# 그래프 탐색을 통해 어떤 섬에 속하는 모든 지점을 찾는 함수
# k는 해당 섬을 나타내는 숫자이다.
def BFS(i, j, k):
    global N
    queue = deque()
    queue.append([i, j])
    visited[i][j] = k
    while queue:
        x, y = queue.popleft()
        for i in range(4):
            next_x = x + dx[i]
            next_y = y + dy[i]
            if 0<=next_x<N and 0<=next_y<N and m[next_x][next_y] == 1 and not visited[next_x][next_y]:
                visited[next_x][next_y] = k
                queue.append([next_x, next_y])
# 어떤 섬의 한 지점에서 다른 섬까지의 최단 거리를 찾는 함수
# k는 해당 섬을 나타내는 숫자이다.
def bridge(i, j, k):
    global N
    queue = deque()
    # queue에 좌표뿐만 아니라 그 좌표까지의 최단 거리도 저장한다.
    queue.append([i, j, 0])
    b_visited[i][j] = True
    while queue:
        x, y, d = queue.popleft()
        for i in range(4):
            next_x = x + dx[i]
            next_y = y + dy[i]
            if 0<=next_x<N and 0<=next_y<N and not b_visited[next_x][next_y]:
                if visited[next_x][next_y] == 0:
                    b_visited[next_x][next_y] = True
                    queue.append([next_x, next_y, d+1])
                # 처음 시작한 섬과 다른 섬에 도착한 경우
                elif visited[next_x][next_y] != k:
                    return d
    return sys.maxsize
# 현재 어떤 섬에 대해 탐색 중인지를 나타내는 변수
cnt = 0
# 각 좌표를 방문했는지, 그리고 육지인 지점인 경우 그 지점이 어느 섬에 속하는지를 저장하는 행렬
visited = [[0]*N for _ in range(N)]
for i in range(N):
    for j in range(N):
        if m[i][j] == 1 and not visited[i][j]:
            cnt += 1
            BFS(i, j, cnt)
# 임의의 두 섬 사이의 최단 거리 중 최솟값을 저장하는 변수
res = sys.maxsize
for i in range(N):
    for j in range(N):
        if visited[i][j]:
            b_visited = [[False]*N for _ in range(N)]
            res = min(res, bridge(i, j, visited[i][j]))
print(res)