[ 42경산 & 알고리즘/자료구조 & 코테 ]
[알고리즘] 최소 스패닝 트리(MST) 개념과 구현: 크루스칼 vs 프림 비교
2024-02-04 23:48:00
TL;DR (세 줄 요약)최소 스패닝 트리(MST)는 그래프의 모든 정점을 사이클 없이 연결하면서, 고른 간선의 가중치 합이 가장 작은 트리입니다.프림 알고리즘은 정점 하나에서 시작해 가장 싼 간선으로 정점을 하나씩 붙입니다. 크루스칼 알고리즘은 모든 간선을 싼 순서로 보면서 사이클을 만들지 않는 간선만 고릅니다.크루스칼에서 사이클이 생기는지는 유니온-파인드로 확인합니다. 백준 1197번은 간선 정렬과 유니온-파인드로 풀었습니다.이 글은 2024년 1월 19일에 백준 1197번 "최소 스패닝 트리" 문제를 풀면서 정리한 기록입니다. 문제를 풀지 못해서 필요한 개념을 처음부터 하나씩 정리했고, 그 순서대로 설명합니다. 코드는 파이썬입니다.1. 어떤 문제를 풀려고 했나요?먼저 용어를 정리합니다. 그래프는 점..