네트워크 연결1 [백준 1922] 네트워크 연결, C++ https://www.acmicpc.net/problem/1922 1922번: 네트워크 연결 이 경우에 1-3, 2-3, 3-4, 4-5, 4-6을 연결하면 주어진 output이 나오게 된다. www.acmicpc.net 본 문제는 최소 스패닝 트리를 구하는 문제다. 최소 스패닝 트리를 구하는 대표적인 방법으로는 prim, kruskal이 있다. 이번 문제는 kruskal을 이용하여 문제를 해결하였다. kruskal을 구현하기 위해선 우선 union-find 자료구조를 구현해야한다. 그리고 간선의 최소 비용을 먼저 연결하면 된다. 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36.. 2020. 2. 17. 이전 1 다음