<프로그래머스> 섬연결하기

문제 출처: programmers.co.kr/learn/courses/30/lessons/42861

코딩테스트 연습 - 섬 연결하기

풀이

각각 섬끼리 연결된 간선의 개수를 구할 수 있고 가중치가 존재하므로 크루스칼 알고리즘을 사용하면 쉽게 풀수있다.

1. 우선 섬끼리 연결된 정보와 가중치를 저장할 객체 클래스를 만든다.

2. 각 섬들이 연결되고 최종적으로 부모?섬이 어디인지 인덱스를 가지고 있는 parents 배열을 생성한다.

3. 처음에는 각 섬들은 스스로를 부모로하도록 parents 배열을 초기화 한다.

4. 가중치가 낮은 것부터 탐색해야 최선의 값(최소값)을 구할 수 있기 때문에 일단 가중치를 기준으로 Sort를 해준다.

5. 각자 섬들을 탐색하여 간선을 연결해주면서 가중치를 더해준다.

 

코드