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

네트워크가 공격 받아서 최소한과 최소 비용으로 네트워크 복구할 수 있게 회선 고르는 문제이다.

Python

시도 1 - 실패

n, m = map(int, input().split())

edges = []

for _ in range(m):
    a, b, c = map(int, input().split())
    edges.append((c, a, b))

edges.sort()


def find_parent(parent, x):
    if parent[x] != x:
        parent[x] = find_parent(parent, parent[x])
    return parent[x]


def union(a, b, parent):
    pa = find_parent(parent, a)
    pb = find_parent(parent, b)

    if pa == pb:
        return False
    else:
        parent[pb] = pa
        return True


parent = [i for i in range(n + 1)]
recover = []

for cost, a, b in edges:
    if union(a, b, parent):
        recover.append((a, b))

print(len(recover))
for a, b in recover:
    print(a, b)

union-find를 활용해서 접근했다. 비용이 가장 작은 회선부터 시작해서 네트워크에 추가했다. 그리고 실패했다.

시도 2 - 다익스트라

from heapq import *
import sys

input = sys.stdin.readline

n, m = map(int, input().split())

adj = [[] for _ in range(n + 1)]

for _ in range(m):
    a, b, c = map(int, input().split())

    adj[b].append((a, c))
    adj[a].append((b, c))


que = []

heappush(que, (0, 1))

dist = [1000 * n] * (n + 1)

dist[1] = 0
parent = [i for i in range(n + 1)]

while que:
    cost, now = heappop(que)

    if dist[now] < cost:
        continue

    for next, d in adj[now]:
        if dist[next] > cost + d:
            dist[next] = cost + d
            parent[next] = now
            heappush(que, (dist[next], next))

edges = []

for idx, now in enumerate(parent):
    if idx == 0 or idx == now:
        continue

    edges.append((min(now, idx), max(now, idx)))

print(len(edges))
for a, b in edges:
    print(a, b)

질문하기를 참고하니까 MST로 접근하던 문제를 다익스트라로 하니까 해결이 됐다는 케이스가 있어서 다익스트라로 다시 풀었다.

parent 리스트를 만들어서 cost가 업데이트 될 때마다 부모를 업데이트했고 마지막에 idx와 부모 노드의 번호를 edges에 담아서 출력했고 통과했다.

문제의 요구사항이 MST를 찾는 것이 아니라 1번 컴퓨터에 보안 시스템 설치하고 1번 컴퓨터로부터 최단 거리를 찾는 문제였기 때문에 다익스트라로 접근해야 됐었다.

문제를 제대로 안 읽고, 그리고 각 알고리즘을 언제 써야하는지를 알지 못해서 실패한 문제였다.