[BOJ 2146] 다리 만들기 (Python)

문제

다리 만들기

---

문제 해설

각 섬을 확장시켜 다른 섬에 닿으면 거리를 출력하는 문제입니다.

1. 각 섬을 넘버링한다.
2. 각 섬을 확장시킨다.

크게 보면 두 가지를 진행하면 됩니다.
먼저 섬을 찾은 후 번호를 매깁니다. 저는 bfs를 활용했고, dfs를 활용해도 됩니다. 이때, 각 섬의 가장 자리의 좌표와 섬의 번호를 ocean에 같이 저장합니다.

그 후 섬을 확장시키면 되는데, 섬의 가장 자리인 ocean에서부터 섬을 한칸씩 확장시키면 됩니다. 저는 여기서 섬에서부터의 거리를 distance라는 2차원 리스트로 저장했습니다.
예시)
graph)
4
1 0 0 1
1 0 0 0
0 0 0 0
0 0 1 0

numbering)
2 0 0 3
2 0 0 0
0 0 0 0
0 0 4 0

1번확장)
graph)
2 2 3 3
2 2 0 3
2 0 4 0
0 4 4 4

distance)
0 1 1 0
0 1 -1 1
1 -1 1 -1
-1 1 0 1

이런 식으로 만약 확장을 진행하다가 다른 섬을 만나게 되면 그때의 distance 값을 리턴해주면 됩니다.

---

풀이 코드

from collections import deque
import sys

input = sys.stdin.readline
n = int(input())

graph = [list(map(int, input().split())) for _ in range(n)]
# 거리 표시. 초기 섬은 0 바다는 -1. 이걸로 다리 길이 표현
distance = [[-1] * n for _ in range(n)]
# ocean 다음 bfs진행할 좌표와 번호 담음
ocean = deque()
dx = -1, 0, 1, 0
dy = 0, 1, 0, -1
num = 2
# 섬 넘버링
def numbering(x, y, num):
    q = deque([(x, y)])
    graph[x][y] = num
    distance[x][y] = 0
    while q:
        x, y = q.popleft()
        for i in range(4):
            nx = x + dx[i]
            ny = y + dy[i]
            if 0 <= nx < n and 0 <= ny < n:
                # 같은 섬일때
                if graph[nx][ny] == 1:
                    graph[nx][ny] = num
                    distance[nx][ny] = 0
                    q.append((nx, ny))
                # 각 섬의 가장자리 좌표 저장
                elif graph[nx][ny] == 0:
                    ocean.append((x, y, num))


# 섬확장
def extend():
    flag = False
    answer = sys.maxsize
    while ocean:
        size = len(ocean)
        for _ in range(size):
            x, y, num = ocean.popleft()
            for i in range(4):
                nx = x + dx[i]
                ny = y + dy[i]
                if 0 <= nx < n and 0 <= ny < n:
                    # 바다의 경우 확장
                    if graph[nx][ny] == 0:
                        graph[nx][ny] = num
                        distance[nx][ny] = distance[x][y] + 1
                        ocean.append((nx, ny, num))
                    # 다른 섬을 만날 경우 종료
                    elif graph[nx][ny] != num:
                        answer = min(answer, distance[x][y] + distance[nx][ny])
                        flag = True
        if flag:
            print(answer)
            return


for i in range(n):
    for j in range(n):
        if graph[i][j] == 1:
            numbering(i, j, num)
            num += 1
extend()

---