Minystory

[Python] 백준 1197 - 최소 스패닝 트리 (Gold 4)

March 20, 2022
Algorithm, Graph
백준, 최소 스패닝 트리, MST, DFS, 크루스칼 알고리즘, 프림 알고리즘, Python, 알고리즘, Union-Find, Heap, 백준 Gold 4
1197번: 최소 스패닝 트리

1197번: 최소 스패닝 트리

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

www.acmicpc.net

해당 문제는 n개의 정점들에 대한 간선들 중에서 가장 가중치가 작은 경로의 가중치를 찾는 것이다.  

정답 풀이보다는 여러가지 방식으로 시도하면서 알고리즘을 발전시키는 과정을 서술한다.

DFS #

처음엔 노드하면 DFS와 BFS 밖에 몰랐기 때문에 당연하게 DFS로 접근했다.