티스토리 뷰
풀이
전형적인 최소신장트리를 만드는 문제이다. 크루스칼 알고리즘, 프림 알고리즘을 사용하여 해결할 수 있느데 여기서는 크루스칼 알고리즘을 사용하였다.
각 섬들의 좌표를 입력받아 Point라는 객체로 만들어 island 리스트에 추가하였다. 즉, island 리스트에는 각 섬들의 x,y 좌표가 들어가 있다. 이제 각각 섬 간의 간선에 대한 가중치를 구하여야 하므로 Edge 클래스를 새로 만들어 주었다. edge리스트는 Edge클래스 자료형으로 저장되고 모든 섬들을 연결하여(중복 제외) 가중치를 저장하였다.
마지막으로 크루스칼 알고리즘을 통해 사이클이 생성되지 않으면서 모든 섬을 연결하여 가중치 합의 최소값을 구하였다.
코드
'알고리즘' 카테고리의 다른 글
| <baekjoon> 미세먼지 안녕 (0) | 2020.09.05 |
|---|---|
| <baekjoon> 최단 경로 (0) | 2020.09.04 |
| <baekjoon> 점프 점프 (0) | 2020.08.31 |
| <baekjoon> 회전하는 큐 (0) | 2020.08.30 |
| <baekjoon> 말이 되고픈 원숭이 (0) | 2020.08.29 |