99클럽 코테 스터디 TIL : 6497 전력난

🚀 문제

https://www.acmicpc.net/problem/6497

🚀 정답 코드

import sys
from collections import deque

input = sys.stdin.readline

# ✅ find: 해당 노드가 속한 집합(루트)을 찾음 + 경로 압축
def find(x):
    if parent[x] != x:
        parent[x] = find(parent[x])
    return parent[x]

# ✅ union: 두 노드를 같은 집합으로 합침 (싸이클이면 False 반환)
def union(x, y):
    x = find(x)
    y = find(y)

    if x == y:  # 이미 같은 집합 → 싸이클 발생
        return False

    parent[y] = x  # y 루트를 x에 붙임
    return True

# ✅ 입력 반복 처리
while True:
    M, N = map(int, input().split())  # M: 집의 개수, N: 도로 수

    if N == 0 and M == 0:
        break  # 종료 조건

    routes = []       # 도로 정보 저장
    total_cost = 0    # 전체 도로 유지 비용

    # ✅ 도로 정보 입력받기
    for _ in range(N):
        r = list(map(int, input().split()))  # u, v, w
        routes.append(r)
        total_cost += r[-1]

    # ✅ 유지비 오름차순 정렬 (Kruskal용)
    routes.sort(key=lambda x: x[-1])

    # ✅ Union-Find 초기화 (자기 자신이 루트)
    parent = [i for i in range(M)]

    route_cost = 0  # MST 비용

    # ✅ Kruskal 알고리즘으로 MST 구성
    for u, v, cost in routes:
        if union(u, v):       # 싸이클이 아니면
            route_cost += cost  # MST에 포함

    # ✅ 절약한 비용 출력 = 전체 비용 - MST 비용
    print(total_cost - route_cost)

🚀 시행착오 했던 부분

최소 스패닝 트리 확인을 위해 현재 그래프가 순환구조가 있는지 검증이 필요한데 처음 시도했던 방식은 매번 그래프를 새로 만들어 시작 노드부터 노드들을 이동하며 검증을 시도했지만, 해당 부분에서 시간 초과가 발생해서 크루스칼 알고리즘을 사용할 때 효과적인 방식인 Union-Find를 찾아보고 해결할 수 있었다.

최소 스패닝 트리 문제를 해결할 때 떠올려야하는 알고리즘으로 Prim, Kruskal 알고리즘이 있는데 이번에 다시 한 번 정리하는 시간을 가졌다.

🔍 Prim 알고리즘 (프림)

• 시작 정점에서 시작해 연결된 가장 가벼운 간선을 선택해 확장
• 우선순위 큐 (heap) 를 사용하여 가장 짧은 간선을 빠르게 선택
• Dense(간선이 많은) 그래프에 적합

복잡도: O(E log V) (인접 리스트 + 힙 사용 시)

🔍 Kruskal 알고리즘 (크루스칼)

• 간선을 가중치 순으로 정렬 후, 싸이클이 생기지 않는 선에서 선택
• 간선이 적은 Sparse 그래프에 유리
• 싸이클 여부 확인을 위해 Union-Find 구조 사용

복잡도: O(E log E)

그리고 이번 문제를 통해서 Union-Find를 사용했는데, 완벽하게 이해했다고 보기 힘들다. 하지만 크루스칼 알고리즘 외에도 집합 관련한 문제를 해결할 때도 사용하는 알고리즘이라고 해서 정리해두면 좋을 것 같다.

🔗 Union-Find (Disjoint Set Union)

• 각 노드가 어느 집합(트리)에 속해 있는지 관리하는 자료구조
• 싸이클 판별이나 집합 병합 등에 사용됨

함수	설명
find(x)	x가 속한 집합의 대표 노드(루트) 를 찾는다
union(x, y)	x, y가 속한 두 집합을 하나로 합친다 (싸이클이 생기면 False)

🔧 union, find 함수 예시 (feat. GPT)

parent = [i for i in range(N)]

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:
        return False  # 싸이클 발생
    parent[y_root] = x_root
    return True