👀 'Do it! 알고리즘 코딩테스트 with Python(김종관 저)'을 공부하고 정리한 내용입니다.

1. 개념

최소 신장 트리란, 그래프에서 모든 노드를 연결할 때 사용된 에지들의 가중치의 합을 최소로 하는 트리입니다. 최소 신장 트리는 사이클이 포함되면 가중치의 합이 최소가 될 수 없으므로 사이클을 포함하지 않으며, N개의 노드가 있으면 최소 신장 트리를 구성하는 에지의 개수는 항상 N-1개 입니다.

2. 원리 이해하기

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

최소 신장 트리는 데이터가 노드가 아닌 에지 중심으로 저장하므로 인접 리스트가 아닌 에지 리스트의 형태로 저장합니다. 이 리스트는 일반적으로 노드 변수 2개와 가중치 변수로 구성됩니다. 사이클 처리를 위한 유니온 파인드 리스트도 함께 초기화합니다. 리스트의 인덱스를 해당 자리의 값으로 초기화하면 됩니다.

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

에지 리스트에 담긴 그래프 데이터를 가중치 기준으로 오름차순 정렬합니다.
오름차순 정렬은 input 데이터의 순서 조정을 통해 높은 자유도로 정렬할 수 있습니다.

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

가중치가 낮은 에지부터 순서대로 선택해 연결을 시도합니다. 이때 바로 연결하지 않고 이 에지를 연결했을 때 그래프에 사이클 형성 유무를 find 연산을 이용해 확인 후 사이클이 형성되지 않을 때문 union 연산을 이용해 두 노드를 연결합니다.

2-4. 과정 3 반복하기

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

2-5. 총 에지 비용 출력하기

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

최소 신장 트리는 다른 그래프 알고리즘과는 달리, 에지 리스트의 형태를 이용해 데이터를 담는다는 특징이 있습니다. 그 이유는 에지를 기준으로 하는 알고리즘이기 때문입니다. 또한 사이클이 존재하면 안되는 특징이 있기 때문에 사이클 판별 알고리즘인 유니온 파인드를 알고리즘 내부에 구현해야합니다.

BOJ 1179 최소 스패닝 트리

문제

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

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

입력

첫째 줄에 정점의 개수 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
from queue import PriorityQueue

input = sys.stdin.readline
N, M = map(int, input().split())

# 우선순위 큐를 사용하여 간선 정보를 저장
pq = PriorityQueue()

# 각 노드의 부모 노드 초기화
parent = [0] * (N + 1)
for i in range(N + 1):
    parent[i] = i

# 간선 정보 입력 및 우선순위 큐에 삽입
for i in range(M):
    s, e, w = map(int, input().split())
    pq.put((w, s, e))  # 가중치를 기준으로 정렬하기 위해 가중치를 맨 앞에 놓음

# 특정 노드의 부모 노드 찾기 함수
def find(a):
    if a == parent[a]:
        return a
    else:
        parent[a] = find(parent[a])  # 경로 압축을 위해 부모 노드를 찾으면서 갱신
        return parent[a]

# 두 노드를 연결하는 함수
def union(a, b):
    a = find(a)
    b = find(b)
    if a != b:  # 사이클이 생성되지 않으면 두 노드 연결
        parent[b] = a

useEdge = 0  # 사용한 간선 수 초기화
result = 0   # 결과값 초기화

# 크루스칼 알고리즘 수행
while useEdge < N - 1:  # 사용한 간선이 N-1개가 될 때까지 반복
    w, s, e = pq.get()  # 가중치가 가장 작은 간선 정보 추출
    if find(s) != find(e):  # 두 노드의 부모가 다르다면 사이클 생성하지 않는다는 의미
        union(s, e)  # 두 노드 연결
        result += w  # 결과값에 가중치 추가
        useEdge += 1  # 사용한 간선 수 증가

print(result)  # 최소 스패닝 트리의 가중치 합 출력