mondegreen

최소 비용을 구하는 문제이다. 먼저 각 섬의 루트노드를 저장할 배열을 선언한다. 이 때 초기 값은 각자의 인덱스 값이다. 즉, 각자가 루트노드인 것이고 각자의 집합에 속해있는 것이다. 그 다음 건설 비용이 적은 순서대로 먼저 정렬해준 후 순서대로 연결을 해본다. 이 때 연결하기 전 두 섬의 연결되어 있는지는 루트 노드를 찾아서 비교한다. 만약 다르다면 다리 연결에 드는 비용을 정답 변수에 더해주고 유니언 메소드를 통해 한쪽 루트노드를 다른 한 쪽으로 변경해서 합쳐준다. 같을 때 다리를 놓는다면 사이클이 생겨 비효율적이고 최소 비용이 될 수 없다. 이 작업을 반복하며 다리의 갯수가 n-1개 일 때 작업을 완료하면 된다. n개를 연결하는 최소 갯수는 n-1개 이기 때문이다. import java.util.*..

최소 신장 트리의 개념 신장 트리 중에서 사용된 간선의 가중치의 합이 최소인 트리' 최소 신장 트리의 특징 1) 무방향 가중치 그래프 2) 그래프 가중치의 합이 최소 3) N개의 정점이 있는 그래프에 대해 반드시 N-1개의 간선을 사용해야 함 4) 사이클을 포함하면 안 된다 => 사이클 포함 = 불필요한 간선 존재 최소 신장 트리의 실 사용 비용이 최소가 되어야 하는 도로망, 통신망과 같은 다양한 분야 최소 신장 트리 구현 1) 크루스칼(Kruskal); 그리디 알고리즘의 한 종류 => 희소 그래프 인 경우 적합 간선을 하나씩 선택하며 MST를 찾는 알고리즘 (1) 모든 간선을 가중치에 따라 오름차순 정렬 (2) 가중치가 낮은 간선부터 선택하며 트리 증가 => 사이클이 존재*하면 그 다음 가중치를 가진 ..