✅ 문제

BOJ 1197번 [최소 스패닝 트리]

그래프가 주어졌을 때, 그 그래프의 최소 스패닝 트리를 구하는 프로그램을 작성하시오.

최소 스패닝 트리는, 주어진 그래프의 모든 정점들을 연결하는 부분 그래프 중에서 그 가중치의 합이 최소인 트리를 말한다.

입력

첫째 줄에 정점의 개수 V(1 ≤ V ≤ 10,000)와 간선의 개수 E(1 ≤ E ≤ 100,000)가 주어진다. 다음 E개의 줄에는 각 간선에 대한 정보를 나타내는 세 정수 A, B, C가 주어진다. 이는 A번 정점과 B번 정점이 가중치 C인 간선으로 연결되어 있다는 의미이다. C는 음수일 수도 있으며, 절댓값이 1,000,000을 넘지 않는다.

그래프의 정점은 1번부터 V번까지 번호가 매겨져 있고, 임의의 두 정점 사이에 경로가 있다. 최소 스패닝 트리의 가중치가 -2,147,483,648보다 크거나 같고, 2,147,483,647보다 작거나 같은 데이터만 입력으로 주어진다.

출력

첫째 줄에 최소 스패닝 트리의 가중치를 출력한다.

💻 코드

import sys
import heapq
input = sys.stdin.readline

V, E = map(int, input().split())
visited = [0] * (V+1)
graph = [[] for _ in range(V+1)]
heap = [(0, 1)]

for _ in range(E):
    s, e, w = map(int, input().split())
    graph[s].append((w, e))
    graph[e].append((w, s))

ans = 0
cnt = 0

while heap:
    if cnt == V:
        break
    w, s = heapq.heappop(heap)
    if not visited[s]:
        visited[s] = 1
        ans += w
        cnt += 1
        for i in graph[s]:
            heapq.heappush(heap, i)

print(ans)

🎯 풀이

• 최소 신장 트리를 구하는 알고리즘에는 크게 2가지 방법이 있다. 하나는 크루스칼 (Kruskal) 알고리즘이고, 하나는 (Prim) 알고리즘이다. 간단하게 요약하자면 크루스칼 알고리즘은 간선들을 오름차순으로 정렬하여 가중치가 작은 간선들을 먼저 선택하되, 사이클을 형성하는 간선은 제외한다. 프림 알고리즘은 시작 정점에서 제일 작은 간선들을 골라나가며, 사이클은 형성하지 않도록 고르는 방식이다. 간선이 많아질 경우에는 프림 알고리즘의 시간 복잡도가 더 효율적이라 이 문제에서는 프림 알고리즘으로 풀었지만, 크루스칼로 풀어도 문제가 없다.

• 위에서 말한 내용을 구현만 하면 된다. 파이썬 같은 경우는 heapq를 통해서 최소힙을 사용하여 풀면 간단하게 풀 수 있다.

• 가중치로 정렬하여 문제를 풀어야 하기 때문에, heap에 추가해줄 때, (정점, 가중치) 형식이 아니라 (가중치, 정점) 형식으로 넣어줘야 기준을 가중치로 잡고 최소힙을 만들어주니 이 점을 주의하면 된다.