prim
-
[BOJ] 1197 최소 스패닝 트리PS/BOJ 2020. 7. 15. 14:29
https://www.acmicpc.net/problem/1197 1197번: 최소 스패닝 트리 첫째 줄에 정점의 개수 V(1 ≤ V ≤ 10,000)와 간선의 개수 E(1 ≤ E ≤ 100,000)가 주어진다. 다음 E개의 줄에는 각 간선에 대한 정보를 나타내는 세 정수 A, B, C가 주어진다. 이는 A번 정점과 B번 정점이 � www.acmicpc.net 알고리즘: MST(Kruskal, Prim) 시간복잡도: O(E*logV) 1. Kruskal (간선 기준): 가중치가 최소인 간선부터 하나씩 선택해가면서 같은 트리에 속해있는지 확인. 같은 트리인지 확인하는건 Union-Find 알고리즘 이용 2. Prim (정점 기준): 정점 기준으로 BFS 돌리기 (가장 작은 가중치를 가진 간선 선택) pri..