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

이 글은 Velog에서 이전한 글입니다. Velog 원문 보기

백준 1197번

처음 시도한 방법
처음에는 그래프 탐색 문제라고 생각해서 DFS로 접근을 했다.
그러나, DFS로 접근시 정점의 개수 V의 범위가 1<=V<=10,000이기 때문에 재귀 오류가 발생할 가능성이 다분하고 시간 초과에 걸린다.

정답 접근법

최소 스패닝 트리(MST) 문제는 전용 알고리즘이 2가지 존재한다.

• 크루스칼 (Kruskal) 알고리즘
  • 간선을 가중치 기준으로 정렬 후, 작은 순서대로 선택하며 Union-Find로 사이클 방지
• 프림 (Prim) 알고리즘
  • 한 노드에서 시작해서 우선순위 큐로 인접 간선 중 최소 선택

내가 사용한 것은 크루스칼 알고리즘이다.

코드 구조

edges = []
for _ in range(E):
    A, B, C = map(int, input().split())
    edges.append((C, A, B))  # 가중치 기준 정렬용

edges.sort()  # 가중치 기준 정렬

# 유니온 파인드 (Disjoint Set) 정의
def find(x):
    ...

def union(x, y):
    ...

total_weight = 0
edge_count = 0
for cost, a, b in edges:
    if find(a) != find(b):
        union(a, b)
        total_weight += cost
        edge_count += 1
        if edge_count == V - 1:
            break

print(total_weight)

알고리즘 절차

1. 모든 간선을 가중치 기준으로 오름차순 정렬
2. 간선 하나씩 선택하면서 다음을 판단:
   • 두 정점이 서로 다른 집합에 있다면 → 연결 가능
   • 두 정점이 같은 집합에 있다면 → 사이클 생기므로 무시
3. 집합을 합친다 (Union)
4. 간선을 V-1개 선택하면 종료

find(x)
→ 정점 x가 속한 집합의 루트 노드를 찾아줌

union(x, y)
→ x, y의 집합이 다르면 합치고 True 반환
→ 같으면 사이클이 생기므로 False 반환

이와 같은 구조로 코드를 짠다면 시간 복잡도가 O(E log E)로 매우 효율적이다.

제출 코드

import sys
input = lambda: sys.stdin.readline().rstrip()

sys.setrecursionlimit(100000)

V, E = map(int, input().split())
edges = []

for _ in range(E):
    A,B,C = map(int, input().split()) # A, B 정점의 가중치 C
    edges.append((C,A,B)) # 가중치 기준으로 정렬 가능하도록

edges.sort()

parent = [i for i in range(V+1)]

def find(x):
    if parent[x] != x:
        parent[x] = find(parent[x])
    return parent[x]

def union(x, y):
    x_root = find(x)
    y_root = find(y)
    if x_root != y_root:
        parent[y_root] = x_root
        return True
    return False

total_weight = 0
for cost, a, b in edges:
    if union(a,b):
        total_weight += cost

print(total_weight)