연휴 보내고 와서, 최근에 공부한 알고리즘을 전부 복기해보며 관련된 문제를 풀어보고 있었다.
그러는 와중에, 풀이를 써보고 싶은 문제가 생겨서 쓰게 되었다. 그 문제가 이 문제!

BOJ 2406 - 안정적인 네트워크 링크
(2022.09.13 기준 G3)
(치팅하면 인터넷 끊김)

문제

본사 컴퓨터(1번)를 제외한 나머지 컴퓨터들이 MST를 이루도록 만들 때에, 필요한 비용과 연결할 컴퓨터들을 출력

알고리즘

한 컴퓨터나 컴퓨터끼리의 한 연결이 고장나도 고장나지 않은 컴퓨터들끼리 경유를 하더라도 전부 연결되어 있어야 하는 경우. 그 중에서도 최소 비용으로 연결해야 하므로, 최소 스패닝 트리

풀이

일단 그냥 뭐 간단한 MST 문제인데, 이 문제는 지문을 잘 이해해야 한다.
중요한 지문만 요약하자면

각 지사의 컴퓨터는 본사와 연결되어 있다.
본사 컴퓨터는 1번이다.

이미 1번 컴퓨터와는 전부 연결되어 있는 상태.
그리고 만약 1번 컴퓨터와의 연결이 전부인 컴퓨터가 있다고 생각하자. 만약, 그 컴퓨터와 1번 컴퓨터와의 연결이 끊어지면 그 컴퓨터는 다른 컴퓨터와의 연결 방법이 없어지게 된다.
그러므로 1번 컴퓨터를 제외하여 다른 한 컴퓨터와도 연결이 되어 있어야 한다.
이는 1번 컴퓨터를 제외하여 MST를 구성하라는 문제인 것이다.

이것말고는 되게 간단한 MST 문제인데, 간선을 정리할 때만 조심하자.
정점 개수가 생각보다 많아 (최대 1,000개), 시간초과가 나기 십상이다.
지문에서 i->j, j->i 둘 다 비용이 같다고 되어 있다. (양방향)
그러므로 간선이 중복되지 않게끔, 잘 정리하자.

for i in range(1, n - 1): # 1번 컴퓨터는 제외
	for j in range(i + 1, n): # 전에 정리한 (i, j) 쌍과 자기 자신으로 가는 방향 제외

이런 느낌으로?

그리고 문제에서 대놓고 크루스칼 알고리즘을 써라고 유도하고 있으니, 웬만하면 크루스칼 쓰자.

코드

# 크루스칼
import sys; input = sys.stdin.readline

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

n, m = map(int, input().split())
parent = list(range(n + 1)) # 부모 노드
ct = 0 # 연결된 간선. 이 수가 (필요한 정점 수 - 1)이 되면 중지해도 무관하다.

# 이미 연결되어 있는 컴퓨터들을 union
for _ in range(m):
    x, y = map(int, input().split())
    if find(x) != find(y): # 단, 부모 노드가 다를 때에 union 한다.
        union(x, y)
        ct += 1
        if ct == n - 2: # 이미 안정적인 네트워크라면, (0, 0)을 출력하고 프로그램 중지
            print(0, 0)
            exit()

# 행렬을 입력받고 간선을 정리
matrix = [list(map(int, input().split())) for _ in range(n)]
edges = []
for i in range(1, n - 1): # 양방향이므로 간선이 중복되지 않게끔 정리하자. 1번 컴퓨터는 제외
    for j in range(i + 1, n):
        edges.append((i + 1, j + 1, matrix[i][j]))

# MST 구성 시작
cost = 0 # 최소비용
connect = [] # 연결할 컴퓨터들의 쌍
for u, v, w in sorted(edges, key = lambda x: x[2]): # 비용 오름차순으로 정렬한 간선으로 차례대로 살펴보자.
    if find(u) != find(v): # 부모 노드가 다르면 union
        union(u, v)
        ct += 1
        cost += w
        connect.append((u, v))
        if ct == n - 2: # 안정적인 네트워크가 되었다면
            print(cost, len(connect)) # 답 출력 후, 중지
            for u, v in connect:
                print(u, v)
            break

여담

난이도가 높아질수록, 문제 독해력이 더 필요해지는 것 같다.
어떤 문제이든 문제를 잘 읽고 풀자!