[백준] 1197번 - 최소 스패닝 트리

---

문제 분석

최소 신장 트리를 묻고 있는 문제로, 최소 신장 트리를 구하여 해결하면 된다.

---

최소 신장 트리의 특징

💡 사이클이 포함되면 가중치의 합이 최소가 될 수 없으므로, 사이클을 포함하지 않는다. N개의 노드가 있으면 최소 신장 트리를 구성하는 에지의 개수는 항상 N-1 개다.

---

최소 신장 트리의 핵심 이론

💡 1. `에지 리스트로 그래프를 구현하고 유니온 파인드 리스트 초기화하기`

최소 신장 트리는 데이터를 노드가 아닌 에지 중심으로 저장하므로 인접 리스트가 아닌 에지리스트의 형태로 저장한다.

이 리스트는 일반적으로 노드 변수 2개와 가중치 변수로 구성된다.

또한, 사이클 처리를 위한 유니온 파인드 리스트를 인덱스의 값과 동일하게 초기화한다.

💡 2. `그래프 데이터를 가중치 기준으로 정렬하기`

에지리스트에 담긴 그래프 데이터를 가중치 기준으로 오름차순 정렬한다.

💡 3. `가중치가 낮은 에지부터 연결 시도하기`

가중치가 낮은 에지부터 순서대로 선택해 연결을 시도한다.

이때 바로 연결하지 않고, 유니온 파인드 리스트를 이용하여 find연산을 통해

두 노드의 find값이 같지 않은 경우(사이클이 형성되지 않는 경우)에만, 두 노드를 연결한다.

그 후, union연산을 통해 두 노드를 연결한다.

💡 4. `과정 3 반복하기`

전체 노드의 개수가 N개이면, 연결한 에지의 개수가 N-1이 될 때까지 과정 3을 반복한다.

💡 5. `총 에지 비용 출력하기`

에지의 개수가 N-1이 되면 알고리즘을 종료하고, 완성된 최소 신장 트리의 총 에지 비용을 출력한다.

---

소스 코드

# 최소 스패닝 트리

import sys
from queue import PriorityQueue
input = sys.stdin.readline

V, E = map(int, input().split())
D = [0] * (V + 1)
for i in range(1, V + 1):
    D[i] = i
edgeCnt = 0
total = 0
queue = PriorityQueue()


def find(idx):
    if idx == D[idx]:
        return idx
    else:
        D[idx] = find(D[idx])
        return D[idx]


for _ in range(E):
    s, e, w = map(int, input().split())
    queue.put((w, s, e))

while edgeCnt < V - 1:
    w, s, e = queue.get()
    if find(s) != find(e):
        edgeCnt += 1
        total += w
        D[find(e)] = D[find(s)]

print(total)