[ 알고리즘 ] 코딩 - Programmers - 섬연결하기.java

---

문제 링크

programmers.co.kr/learn/courses/30/lessons/42861

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

---

* 프로그래머스 - Level 3 - (자바)섬 연결하기 - 기본적인 크루스칼

입출력예시

사이클이 생기지 않도록 최단 경로를 찾으면 된다

 

---

< 로직 >

* 기본적인 크루스칼과 같다

* 모든 간선을 가중치 기준으로 정렬

* 출발지와 도착지의 집합을 비교

* 서로 다른 집합이라면 하나의 집합으로 합침

* 반복

---

import java.util.Comparator;
import java.util.PriorityQueue;

public class 섬연결하기 {
	static class Solution {
	    static class Island {
	    	int from, to, weight;

			public Island(int from, int to, int weight) {
				this.from = from; // 출발지
				this.to = to; // 목적지
				this.weight = weight; // 가중치
			}
	    }
		public int solution(int n, int[][] costs) {
			PriorityQueue<Island> pQueue = new PriorityQueue<Island>(new Comparator<Island>() {
				@Override
				public int compare(Island o1, Island o2) {
					return Integer.compare(o1.weight, o2.weight);
				}
			});
			
			for(int i = 0; i < costs.length; i++) {
				  pQueue.offer(new Island(costs[i][0],costs[i][1],costs[i][2]));
			}
			
			int parent[] = new int[n+1];
			make(parent, n); // 서로소 만들기
			
			int answer = 0;
			int cnt = 0;
			
			while(!pQueue.isEmpty()) {
				Island curIsland = pQueue.poll();
				if(union(parent, curIsland.from, curIsland.to)) {
					answer += curIsland.weight;
					if(++cnt == n+1) break;
				}
				
			}
	       
	        return answer;
	    }
		
		/** 합집합 만들기 */
		private boolean union(int[] parent, int first, int sec) {
			int aroot = find(parent, first);
			int broot = find(parent, sec);
			
			if(aroot == broot) return false;
			parent[broot] = aroot;
			return true;
		}

		/** 자신이 속한 집합 찾기 */
		private int find(int[] parent, int num) {
			if(parent[num] == num) return num;
			return parent[num] = find(parent, parent[num]);
		}

		/** 서로소 만들기 */
		private void make(int[] parent, int n) {
			for(int i = 1; i < n; i++) {
				parent[i] = i;
			}
		}
	}