2026-01-07

오늘 한 일

백준 1197 – 최소 스패닝 트리(MST)

• 그래프의 모든 정점을 연결
• 사이클 없이
• 간선 가중치 합이 최소가 되는 트리
• 정점이 V개면 간선은 V-1개

핵심 개념

MST의 목적

• 최단 경로 문제가 아님
• 전체 그래프를 최소 비용으로 연결하는 구조

크루스칼 알고리즘

1. 모든 간선을 가중치 기준 오름차순 정렬
2. 가중치가 가장 작은 간선부터 확인
3. 사이클이 생기지 않으면 선택
4. 간선이 V-1개가 되면 종료

Union-Find로 사이클 판별

• 각 정점은 처음에 자기 자신이 부모
• 두 정점의 대표가 같으면 사이클
• 다르면 union 후 간선 채택

느낀 점

• 오래 전에 공부한 알고리즘이라 개념이 흐릿했다. 큰일이다.
• 크루스칼과 Union-Find를 같이 복습할 수 있었다.