[Gold IV] 최소 스패닝 트리 - 1197

문제 링크

성능 요약

메모리: 53736 KB, 시간: 384 ms

분류

최소 스패닝 트리, 그래프 이론

문제 설명

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

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

입력

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

출력

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

---

문제 풀이

문제 분석

문제는 그래프가 주어졌을 때, 최소 스패닝 트리(Minimum Spanning Tree, MST)의 가중치 합을 구하는 것입니다. 입력으로는 정점의 개수 V, 간선의 개수 E, 그리고 각 간선을 나타내는 정점 A, B와 가중치 C가 주어집니다. 출력은 MST의 가중치 합입니다.

접근 방법

최소 스패닝 트리를 구하는 대표적인 알고리즘인 크루스칼(Kruskal) 알고리즘을 사용합니다. 크루스칼 알고리즘은 다음과 같은 과정을 거칩니다.

1. 모든 간선을 가중치 기준으로 오름차순 정렬합니다.
2. 가중치가 가장 작은 간선부터 선택하면서, 해당 간선을 추가했을 때 사이클이 생기지 않으면 MST에 추가합니다.
3. 모든 정점이 연결될 때까지 2번 과정을 반복합니다.

사이클을 확인하기 위해 Union-Find 자료구조를 사용합니다. Union-Find는 각 정점이 속한 집합을 관리하며, find 연산을 통해 각 정점의 루트 노드를 찾고, union 연산을 통해 두 정점이 속한 집합을 합쳐줍니다.

구현 설명

1. Union-Find 초기화

• parents = {} : 각 정점의 부모 정보를 저장할 딕셔너리를 초기화합니다. 처음에는 각 정점이 자기 자신을 부모로 가리키도록 설정합니다 (make-set 연산).

2. Find 연산 구현

• find(x) : 정점 x가 속한 집합의 루트 노드를 찾는 함수입니다.
  • if x not in parents: : x가 parents에 없으면(처음 등장한 정점), parents[x] = x를 통해 자기 자신을 부모로 설정합니다.
  • if parents[x] != x: : x의 부모가 x 자신이 아니면(루트 노드가 아니면), 재귀적으로 parents[x]의 루트 노드를 찾아 x의 부모로 갱신합니다 (경로 압축). 경로 압축은 find 연산의 성능을 향상시키는 데 기여합니다.

3. Union 연산 구현

• union(a, b) : 정점 a와 b가 속한 집합을 합치는 함수입니다.
  • a = find(a) : 정점 a의 루트 노드를 찾습니다.
  • b = find(b) : 정점 b의 루트 노드를 찾습니다.
  • if not a == b: : a와 b의 루트 노드가 다르면(서로 다른 집합에 속하면), parents[a] = b를 통해 a가 속한 집합을 b가 속한 집합에 합칩니다.

4. 크루스칼 알고리즘 실행

• 간선 정보를 입력받아 arr 리스트에 저장합니다. 각 간선은 [가중치, 정점 A, 정점 B] 형태로 저장됩니다.
• arr.sort() : 간선들을 가중치를 기준으로 오름차순 정렬합니다.
• answer = 0 : MST 가중치 합을 저장할 변수를 초기화합니다.
• 정렬된 간선들을 순회하면서, 각 간선에 대해 find(x) == find(y)를 통해 두 정점이 이미 같은 집합에 속해 있는지 확인합니다. 만약 두 정점이 서로 다른 집합에 속해 있다면(사이클이 생기지 않는다면), union(x, y)를 호출하여 두 집합을 합치고, 현재 간선의 가중치를 answer에 더합니다.
• 최종적으로 answer를 출력합니다.

⏱복잡도 분석

• 시간 복잡도:
  • 간선 정렬: O(E log E)
  • Union-Find 연산: O(E α(V)), 여기서 α(V)는 Ackermann 함수의 역함수로, 매우 느리게 증가하므로 사실상 상수 시간에 가깝습니다.
  • 전체 시간 복잡도: O(E log E) + O(E α(V)) ≈ O(E log E) (E는 간선 수, V는 정점 수)
• 공간 복잡도:
  • parents 딕셔너리: O(V)
  • arr 리스트: O(E)
  • 전체 공간 복잡도: O(V + E)

핵심 포인트

1. 크루스칼 알고리즘: 최소 스패닝 트리를 구하는 효율적인 알고리즘이며, 탐욕적인(greedy) 접근 방식을 사용합니다.
2. Union-Find 자료구조: 사이클을 효율적으로 검사하고, 정점들이 속한 집합을 관리하는 데 필수적입니다. 경로 압축(Path Compression)을 통해 성능을 향상시킬 수 있습니다.
3. 간선 정렬: 가중치가 낮은 간선부터 선택해야 하므로, 간선들을 가중치 기준으로 정렬하는 것이 중요합니다.

풀이 코드

import sys
sys.setrecursionlimit(10**6)

input = sys.stdin.readline

parents = {}
def find(x):
    if x not in parents:
        parents[x] = x

    if parents[x] != x:
        parents[x] = find(parents[x])

    return parents[x]

def union(a,b):
    a = find(a)
    b = find(b)
    if not a == b:
        parents[a] = b

n,m = map(int, input().split())

arr = []
for i in range(m):
    x,y,w = map(int, input().split())
    arr.append([w,x,y])

arr.sort()

answer = 0
for w,x,y in arr:
    if not find(x) == find(y):
        union(x,y)
        answer += w

print(answer)