Kruskal2 boj 1197 - 최소 스패닝 트리(MST, kruskal) 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를 구할 때 사용하는 알고리즘은 프림, 크루스칼 알고리즘이 있다. (V, E)가 각각 그래프의 노드, 엣지의 갯수 일때 노드를 기준으로 MST를 찾아나가는 프림 알고리즘은 은 복잡도가 O(V*E) = O(V^3)이고, 엣지를 기준으로 Disjoint set을 합치면서 사이클이 생기지 않았는지 검사하는 union-find 알고리즘을 이용하면 복잡도가 O(Elog.. 2021. 3. 28. 1922- 네트워크 연결 C++(MST, prim or kruskal, BFS) www.acmicpc.net/problem/1922 1922번: 네트워크 연결 이 경우에 1-3, 2-3, 3-4, 4-5, 4-6을 연결하면 주어진 output이 나오게 된다. www.acmicpc.net 최소 스패닝 트리를 만드는 문제이다. MST를 구하는 알고리즘에는 프림, 크루스칼 알고리즘이 있는데, 그 중 정점을 기준으로 최소비용 엣지을 추가해나가며 MST를 만들어나가는 프림 알고리즘을 이용했다. 크루스칼 알고리즘은 간선을 기준으로 사이클이 만들어지는 지 여부를 union-find 알고리즘으로 파악해나가면서 최소비용 엣지을 MST에 추가해 나가는 알고리즘이다. priority_queue을 이용해서 특정 노드에서 갈 수 있는 엣지의 최소값을 찾아내고, bfs를 하면서 방문해나간다. 우선순위 큐를 .. 2021. 3. 28. 이전 1 다음
