문제설명

• n 개의 섬 사이에 다리를 건설할 비용 costs 배열이 주어지고 최소 비용을 반환해야한다.

제한사항

• n 은 1 이상 100 이하이다.
• costs 길이는 ((n-1) * n) / 2 이하이다.
• costs 요소에는 순서대로 두 섬의 번호, 두 섬을 연결하는데 드는 비용이 들어있다.
• 같은 연결은 두 번 주어지지 않고 순서가 바뀌어도 같은 연결로 취급한다.
• 건설 비용이 없거나 건설이 불가능하거나 연결할 수 없는 섬이 주어지지 않는다.

문제풀이

체크포인트

• 최소 비용을 구하기 위해 비용을 기준으로 오름차순으로 정렬한다.
• CycleTable 을 만들어 Find-Union 알고리즘을 구현한다.
• 0 부터 n 만큼의 사이클 테이블을 만든다.
• 섬의 번호도 0 부터 시작하기 때문에 테이블의 인덱스는 섬의 번호와 동일하다.
• 두 섬의 번호에 해당하는 테이블의 값이 서로 다를 경우 두번째 값을 첫번째 값으로 바꿔준다.
• 이 과정에서 테이블 내에 동일한 값은 서로 연결된 상태를 의미한다.
• 결과적으로 테이블 값이 하나의 숫자로 통일되고 모든 다리가 연결되었음을 의미한다.