다리 만들기에 이어서 다리 만들기 2를 풀이해보겠다.

BOJ 17472 - 다리 만들기 2 링크
(2022.09.21 기준 G1)
(치팅하면 칼퇴 못함)

문제

육지가 1, 바다가 0인 지도가 주어진다면, 섬끼리 잇는 '길이가 최소 2 이상이고 일직선인' 다리를 놓아 모든 섬을 연결시킨다고 했을 때, 모든 섬을 연결하는 다리의 길이 합의 최솟값.

알고리즘

이어진 육지끼리 한 섬으로 만들고 (플러드 필), 섬 사이의 가능한 다리들을 BFS로 찾아서 모든 섬이 이어지게끔 MST를 만들면 된다.

풀이

이어진 육지끼리 한 섬으로 만들고, 섬 사이의 거리를 찾는 과정은 다리 만들기와 거의 동일하다.
다른 점은, 방향이 동일하게 다리가 나아가야 하고, 다리 길이는 무조건 2 이상.
그러므로 섬 테두리의 위치를 따로 queue에 담을 땐, 방향도 같이 담아주면 된다.
그리고 다리 길이가 2 이상이 되었을 때만 간선을 저장하면 된다.

MST를 만드는 방법은 2가지이다. 정점 위주의 프림, 간선 위주의 크루스칼.
두 방법 모두 설명해보겠다.

• 프림
  먼저 i에서 j로 갈 때의 최단 길이를 담는 인접 행렬을 inf로 초기화하여 섬의 개수만큼 만든다.
  그리고 따로 저장한 queue로, 탐색을 하여 다른 섬에 도달한다면 시작 섬과 도착 섬 사이의 최단 경로를 갱신해주자. 물론, 양방향으로 말이다. (굳이 양방향이 아니어도 될 듯)
  그리고 첫번째 섬부터 시작하여 연결된 섬으로 하여금 탐색하여 프림 알고리즘을 돌려 MST를 완성해주자.
  
  
• 크루스칼
  따로 저장한 queue로, 탐색을 하여 다른 섬에 도달할 때마다 (길이, 시작 섬, 도착 섬)을 edges에 저장하자. 모든 탐색이 끝나면 edges를 길이가 오름차순이 되게 정렬하여 차례대로 살펴보면서 find, union 함수를 이용하여 크루스칼 알고리즘을 돌려 MST를 완성해주자.
  
  

자세한 설명은 코드에 주석을 달았으니 참고하면서 보자.

코드

import sys; input = sys.stdin.readline
from math import inf
from collections import deque

N, M = map(int, input().split()) # 지도의 크기
matrix = [list(map(int, input().split())) for _ in range(N)] # 지도

island = 2 # 0 - 바다, 1 - 육지이므로 2번부터 넘버링
queue = deque() # 섬 끝에서 다른 섬으로 탐색 시작하는 위치를 저장
for n in range(N):
    for m in range(M):
        if matrix[n][m] == 1: # 방문하지 않은 육지이면
            # 플러드 필 시작
            matrix[n][m] = island # 시작 위치부터 먼저 넘버링 후 덱에 담자.
            fill = deque([(n, m)])
            # 방문체크는 넘버링이 있기 때문에 따로 visited 배열을 쓰지 않아도 된다.
            while fill:
                i, j = fill.popleft()
                for di, dj in [(-1, 0), (1, 0), (0, -1), (0, 1)]: # 상하좌우 방향
                    if 0 <= i + di < N and 0 <= j + dj < M: # 지도의 범위 안이어야 한다.
                        if matrix[i + di][j + dj] == 1: # 만약 다음 위치가 방문하지 않은 육지이면
                            matrix[i + di][j + dj] = island # 넘버링을 해주고 덱에 넣는다.
                            fill.append((i + di, j + dj))
                        elif not matrix[i + di][j + dj]: # 만약 다음 위치가 바다이면
                            queue.append((i + di, j + dj, di, dj, 1, island)) # 현재 위치가 섬 끝이므로 탐색 시작하는 위치로 저장하자.
            # 한 섬의 플러드 필이 끝났다면 섬 번호는 1 증가시키자.
            island += 1

프림과 크루스칼 중 하나를 선택

• 프림

import heapq

total = island - 2 # 넘버링은 2부터 시작했으므로, 총 섬의 개수는 빼기 2를 해주면 된다.
graph = [[inf] * total for _ in range(total)] # 각 섬마다 다른 섬으로 연결된 최소 길이의 다리
# 따로 저장해두었던 queue로, 각 섬들이 다른 섬으로 이어지게끔 탐색 시작
while queue:
    i, j, di, dj, length, start = queue.popleft() # 위치 i, j, 방향 di, dj, 다리길이, 시작 섬
    if 0 <= i + di < N and 0 <= j + dj < M: # 지도의 범위 안이어야 한다.
        if not matrix[i + di][j + dj]: # 만약 다음 위치가 바다이면
            queue.append((i + di, j + dj, di, dj, length + 1, start)) # 한 칸 전진
        elif matrix[i + di][j + dj] != start and length > 1: # 다음 위치가 바다도 시작 섬도 아니고 다리 길이가 2 이상이면
            s = start - 2; e = matrix[i + di][j + dj] - 2 # 넘버링은 2부터 시작했으므로 빼기 2를 해주자.
            # 시작 섬과 도착 섬의 연결하는 다리의 길이를 최솟값으로 갱신
            # 양방향으로 갱신하자.
            graph[s][e] = min(graph[s][e], length)
            graph[e][s] = min(graph[e][s], length)
        # 위 두 if문에 해당하지 않으면 다리가 시작한 섬이랑 만난 것이므로 패스
queue = [[0, 0]] # 0번부터 시작
visited = [False] * total
answer = 0; ct = 0 # 모든 섬을 연결하는 다리 길이 (MST 비용), 연결된 정점 개수
while queue:
    w, u = heapq.heappop(queue)
    if visited[u]: # 방문한 정점이면 패스
        continue
    visited[u] = True # 방문 체크
    answer += w # 가중치(길이)를 더하고
    ct += 1 # 연결된 정점 개수에 1을 더한다.
    if ct == total: # 만약 모든 정점이 연결이 되었다면 MST 완성
        print(answer) # 답을 출력 후 중지
        break
    for v, ww in enumerate(graph[u]):
        if not visited[v] and ww < inf: # 방문하지 않은 정점이고 가중치(길이)가 inf 미만일 경우(연결 가능할 경우)
            heapq.heappush(queue, [ww, v])
else: # 만약 queue가 비었는데 MST가 완성되지 않았다면
    print(-1) # -1 출력

• 크루스칼

def find(u):
    if parent[u] != u:
        parent[u] = find(parent[u])
    return parent[u]

def union(u, v):
    u = find(u)
    v = find(v)
    if u < v:
        parent[v] = u
    else:
        parent[u] = v

total = island - 2 # 넘버링은 2부터 시작했으므로, 총 섬의 개수는 빼기 2를 해주면 된다.
edges = [] # 섬끼리 잇는 다리(간선)를 저장
# 따로 저장해두었던 queue로, 각 섬들이 다른 섬으로 이어지게끔 탐색 시작
while queue:
    i, j, di, dj, length, start = queue.popleft() # 위치 i, j, 방향 di, dj, 다리길이, 시작 섬
    if 0 <= i + di < N and 0 <= j + dj < M: # 지도의 범위 안이어야 한다.
        if not matrix[i + di][j + dj]: # 만약 다음 위치가 바다이면
            queue.append((i + di, j + dj, di, dj, length + 1, start)) # 한 칸 전진
        elif matrix[i + di][j + dj] != start and length > 1: # 다음 위치가 바다도 시작 섬도 아니고 다리 길이가 2 이상이면
            s = start - 2; e = matrix[i + di][j + dj] - 2 # 넘버링은 2부터 시작했으므로 빼기 2를 해주자.
            edges.append((length, s, e)) # (가중치, 시작, 끝)을 저장
        # 위 두 if문에 해당하지 않으면 다리가 시작한 섬이랑 만난 것이므로 패스
parent = list(range(total)) # 부모 노드
answer = 0; ct = 0 # 모든 섬을 연결하는 다리 길이 (MST 비용), 연결된 간선 개수
for w, u, v in sorted(edges): # 가중치가 오름차순이 되게끔 정렬한 간선들을 차례대로 살펴보자.
    if find(u) != find(v): # 부모 노드가 다르면 union
        union(u, v)
        answer += w # 가중치(길이)를 더하고
        ct += 1 # 연결된 간선 개수에 1을 더한다.
        if ct == total - 1: # 만약 모든 섬이 연결이 되었다면 MST가 완성
            print(answer) # 답을 출력 후 중지
            break
else: # 만약 queue가 비었는데 MST가 완성되지 않았다면
    print(-1) # -1 출력

여담

위가 크루스칼, 밑이 프림이다.
완전 별 차이 없다. 그냥 풀고 싶은 방식대로 풀면 될 듯?
(그렇다고 모든 문제에서 크루스칼이랑 프림이 비슷하진 않다. 정점의 수와 간선의 수를 잘 보고 어떤 방법으로 풀지 잘 선택할 것!)