가장 싸게 다 잇자냥! 최소 신장 트리

• 신장 트리와 최소 신장 트리가 뭔지 안다.
• 크루스칼로 MST 를 만든다.
• 연결이 안 되는 경우를 판별한다.
• MST 의 가장 비싼 간선을 활용한다.
• 이미 놓인 간선이 있을 때 응용한다.

비유로 이해하기 — 마을에 수도관 깔기

집 n채를 수도관으로 다 이어야 한다냥. 모든 집에 물이 가되, 관 놓는 비용은 최소로 하고 싶다냥.

고리(사이클)를 만들면 낭비라냥 — 이미 이어진 집을 또 잇는 거니까라냥. 그래서 사이클 없이, 딱 n-1개의 관으로, 가장 싸게 잇는 게 MST 라냥.

16장의 유니온 파인드가 그대로라냥.

"두 끝이 같은 무리냥?" 이 바로 16장의 사이클 판별이라냥. find(u) != find(v) 면 잇고, 같으면 버린다냥. 크루스칼은 정렬 + 유니온 파인드일 뿐이라냥.

정렬을 빼먹으면 최소가 아니다냥.

싼 간선부터 봐야 최소 비용이 된다냥. 정렬 없이 입력 순서대로 더하면 그냥 아무 신장 트리일 뿐, 최소가 아니라냥. 오늘 1번 문제가 이걸 잡는다냥.

쓴 간선이 정확히 n-1개인지 세면 된다냥.

신장 트리는 간선이 딱 n-1개라냥. 크루스칼이 끝났는데 쓴 간선이 그보다 적으면, 모두를 잇지 못한 거라냥.

used = 0
# ... 간선을 쓸 때마다 used += 1
print(total if used == n - 1 else -1)

오늘 2번 문제가 이거라냥. 연결이 안 되면 -1 을 출력한다냥.

"쓴 간선 수" 대신 "남은 무리 수"를 세도 된다냥. 크루스칼이 끝난 뒤 대표가 자기 자신인 노드가 하나뿐이면 다 이어진 거라냥.

간선을 오름차순으로 보니, MST 에 실제로 쓴 간선 중 마지막이 가장 비싸다냥. 그냥 mx = w 로 계속 덮어쓰면 자동으로 최댓값이 남는다냥.

이미 놓인 간선으로 무리가 줄었으니, 필요한 추가 간선도 그만큼 줄어든다냥. "쓴 간선 수 == (남은 무리 수) - 1" 이면 다 이어진 거라냥.

오늘 5번 문제가 이거라냥. 16장의 union 을 크루스칼 앞에 붙이면 끝이라냥.