Kruskal
-
[BOJ] 1647 도시 분할 계획PS/BOJ 2020. 7. 16. 17:03
https://www.acmicpc.net/problem/1647 1647번: 도시 분할 계획 첫째 줄에 집의 개수N, 길의 개수M이 주어진다. N은 2이상 100,000이하인 정수이고, M은 1이상 1,000,000이하인 정수이다. 그 다음 줄부터 M줄에 걸쳐 길의 정보가 A B C 세 개의 정수로 주어지는데 A번 집 www.acmicpc.net 알고리즘: MST (Kruskal) 시간복잡도: O(MlogM) 접근: 1. 각 분리된 마을 안에 있는 임의의 두 집 사이에 경로가 항상 존재해야 한다. 2. 그 경로의 합은 최소가 되야 한다. 3. 분리된 마을은 2개 -> 1, 2번 조건을 통해 이 문제는 MST의 변형 문제라는 것을 알 수 있다. 다만 기존 MST 문제와 차이점은 두 마을로 만들어야 한다는..
-
[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..