[Python] 백준 2146번 다리 만들기

문제

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

입력

• 첫 줄에는 지도의 크기 N(100이하의 자연수)가 주어진다. 그 다음 N줄에는 N개의 숫자가 빈칸을 사이에 두고 주어지며, 0은 바다, 1은 육지를 나타낸다. 항상 두 개 이상의 섬이 있는 데이터만 입력으로 주어진다.

출력

• 첫째 줄에 가장 짧은 다리의 길이를 출력한다.

입력 예제

10
1 1 1 0 0 0 0 1 1 1
1 1 1 1 0 0 0 0 1 1
1 0 1 1 0 0 0 0 1 1
0 0 1 1 1 0 0 0 0 1
0 0 0 1 0 0 0 0 0 1
0 0 0 0 0 0 0 0 0 1
0 0 0 0 0 0 0 0 0 0
0 0 0 0 1 1 0 0 0 0
0 0 0 0 1 1 1 0 0 0
0 0 0 0 0 0 0 0 0 0

출력 예제

3

문제 풀이

• BFS를 총 두 번 돌려서 해결
  • 각 섬별로 번호 부여하기
  • 각 섬에서 다른 섬으로 이동하는 거리 탐색하기
• 바다가 0, 육지가 1이므로 섬 넘버링은 2번부터 시작한다.
  • 2번부터 시작해서 각 섬별로 섬의 번호 부여
• 각 섬별로 번호룰 부여했다면 이제 다리를 놓을 수 있는 최소 거리를 구해야한다.
  • 매개변수로 받은 숫자를 부여받은 섬이라면 좌표를 모두 큐에 넣는다
  • 큐에 섬2의 모든좌표, 섬3의 모든좌표와 같이 모든 값이 들어간다.
  • 탐색시작 -> pop한 값의 좌표부터 BFS 돌리면서 아직 방문하지 않은 바다라면 거리 갱신
  • pop한 값이 다른 섬이라면 리턴 -> 이 때 다른 섬의 거리는 포함하지 않아야하므로 그냥 이전까지 탐색했던 최소거리를 리턴했다.
• 섬 번호 별로 탐색한 최소 거리를 비교하며 그 중에서도 가장 최솟값을 찾아 갱신 후 출력한다.

코드

from collections import deque

# 상하좌우
dy = [-1,1,0,0]
dx = [0,0,-1,1]

n = int(input())
graph = [[] * n for _ in range(n)]

for i in range(n):
    graph[i] = list(map(int, input().split()))


def island_numbering(y, x, num):
    queue = deque()
    queue.append((y, x))
    graph[y][x] = num

    while queue:
        y, x = queue.popleft()
        for i in range(4):
            ny = y + dy[i]
            nx = x + dx[i]
            # 범위 체크
            if 0 <= ny < n and 0 <= nx < n and graph[ny][nx] == 1:
                graph[ny][nx] = num
                queue.append((ny, nx))

def building_bridge(num):
    dist = [[0] * n for _ in range(n)]
    # num 번호를 가진 대륙 찾기
    queue = deque()
    for i in range(n):
        for j in range(n):
            if graph[i][j] == num:
                queue.append((i, j))

    # 다리 놓으면서 거리 찾기
    while queue:
        y, x = queue.popleft()
        for i in range(4):
            ny = y + dy[i]
            nx = x + dx[i]
            # 범위 체크
            if 0 <= ny < n and 0 <= nx < n:
                # 다른 도시를 만났을 경우 리턴
                if graph[ny][nx] != num and graph[ny][nx] != 0:
                    return dist[y][x]

                # 아직 가지 않은 바다인 경우
                if graph[ny][nx] == 0 and dist[ny][nx] == 0:
                    dist[ny][nx] = dist[y][x] + 1
                    queue.append((ny, nx))

# 육지 찾아서 섬 번호 넘버링
num = 2
for i in range(n):
    for j in range(n):
        if graph[i][j] == 1:
            island_numbering(i,j,num)
            num += 1

# 각 섬마다 다리 놓기
result = 10001
for i in range(2, num):
    distance = building_bridge(i)
    result = min(result,distance)

print(result)