1922번: 네트워크 연결 이 경우에 1-3, 2-3, 3-4, 4-5, 4-6을 연결하면 주어진 output이 나오게 된다. www.acmicpc.net 문제 요약 모든 컴퓨터를 연결하는데 필요한 최소 비용을 출력한다. 접근 1. BFS 최소 비용이면 BFS라고 생각할수 있겠지만 시작점에서 특정 지점까지의 최소 거리이므로 조건과 맞지않다. (몇몇 조건은 만족할수 있다.) 2. MST(Minimum Spanning Tree) 최소신장트리 사용된 간선들의 가중치 합이 최소인 트리이다. 신장트리를 만들때 최소의 간선을 사용해서 모든 노드를 방문해야 하고, 사이클을 만들지 않아야한다. Kruskal 낮은 비용의 간선부터 차례로 선택함 사이클이 생기는 간선은 제거함(cycle이 만들어지는지 확인 필요, ex. ..