코딩테스트/백준
[코테] 백준 1922번 : 네트워크 연결 (java)
https://www.acmicpc.net/problem/1922알고리즘 분류 : 그래프 이론, 최소 스패닝 트리❓문제🔅해석컴퓨터 == 정점선 == 간선 모든 컴퓨터(정점)를 연결하여 최소의 비용(가중치)을 얻기 위해 MST를 구현한다.MST를 구하기 위한 알고리즘에는 크루스칼, 프림이 있는데 크루스칼로 풀이해본다. // input691 2 51 3 42 3 22 4 73 4 63 5 114 5 34 6 85 6 8 1. 간선 정렬그래프의 모든 간선을 가중치 기준으로 오름차순 정렬한다. 2. 간선 선택정렬된 간선 리스트에서 순차적으로 간선을 선택한다. 이때, 선택된 간선이 사이클을 형성하지 않는다면 해당 간선을 최소 신장 트리에 추가한다. 3. 사이클 검증사이클이 형성되는지 확인하기 위해서 유니온-..
