최소 스패닝 트리 - 그래프 탐색 기본, 서로소 집합 알고리즘

조해빈·2023년 3월 19일

백준

목록 보기

30/53

문제

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

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

입력
첫째 줄에 정점의 개수 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보다 작거나 같은 데이터만 입력으로 주어진다.

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

풀이

크루스칼 알고리즘Kruskal's Algorithm을 사용하여 주어진 그래프에서 최소 비용 신장 트리(Minimum Spanning Tree)를 찾는 알고리즘이다.

크루스칼 알고리즘

그래프의 간선을 가중치의 오름차순으로 정렬한 뒤,
가중치가 작은 간선부터 하나씩 선택하면서 신장 트리를 구성한다. 이때 선택한 간선이 사이클을 형성하는 경우, 해당 간선은 버리고 다음으로 작은 가중치의 간선을 선택.
이를 모든 간선이 선택될 때까지 반복한다.

다음의 코드는 정답이다.

import sys
input = sys.stdin.readline
V, E = map(int, input().split()) 

edge = []
for _ in range(E):
    a, b, w = map(int, input().split())
    edge.append((w, a, b))    # 입력으로 주어진 V개의 정점과 S개의 간선을 edge 리스트에 저장. 각 원소는 (간선 가중치, 출발 정점, 도착 정점)의 형태.

edge.sort(key=lambda x: x[0]) # 가중치의 오름차순으로 정렬.

parent = list(range(V + 1))   # 각 정점의 부모가 자기 자신으로 초기화.

def findParent(a): # 중간 경로의 모든 정점의 부모를 최상위 부모로 갱신해주고 있다. 루트 노드가 아니라면, 루트 노드를 찾을 때까지 재귀적으로 부모를 호출.
    if a == parent[a]:
        return a
    parent[a] = findParent(parent[a])
    return parent[a]

def unionParent(a, b): # 두 원소가 속한 집합을 합친다.
    a = findParent(a)
    b = findParent(b)
    if b < a:
        parent[a] = b
    else:
        parent[b] = a

sum = 0

for w, s, e in edge:
    if findParent(s) != findParent(e): # edge 리스트를 가중치의 오름차순으로 순회하면서 각각의 간선을 선택하면서 최소 비용 신장 트리를 구성합니다. 
   									   # 이때, 선택한 간선의 두 정점이 이미 같은 집합에 속해 있으면 사이클을 형성하므로 해당 간선은 선택하지 않고 다음으로 작은 가중치의 간선을 선택합니다.
        unionParent(s, e)
        sum += w           # 선택한 간선들의 가중치 합을 출력. 

print(sum)

동기 중 가장 알고리즘 풀이에 익숙한 형인님이 말하길 이건 그냥 외우라고 했다...

위 코드 중 findParent(), unionParent() 함수는 서로소 집합 알고리즘이다. 문제에서 말했듯 최소 스패닝 트리란 "주어진 그래프의 모든 정점들을 연결하는 그 가중치의 합이 최소인 경우"의 트리이다. 이를 찾기 위해선 서로소 집합 알고리즘을 이해해야 한다.