[프로그래머스] 섬 연결하기

프로그래머스 level 3 섬 연결하기

 

이상하게 코드를 짜다가 이게 MST구하는 크루스칼 문제라는 걸 나중에 꺠달았다..

그래프를 한 지 오래 되어서 기억이 나지 않아

옛날에 공부했던 크루스칼 코드를 다시 보고 짤 수 있었다.

 

코드는 기본 크루스칼 코드와 다른 점이 전혀 없다!!!

import java.util.ArrayList;
import java.util.Collections;
import java.util.Comparator;
import java.util.List;
class Solution {
    public static int solution(int n, int[][] costs) {
    	N = n;
    	List<int[]> adjList = new ArrayList<>();
    	for (int i = 0; i < costs.length; i++) {
    		adjList.add(new int[] {costs[i][0], costs[i][1], costs[i][2]});
    	}

    	makeSet();
    	
    	Collections.sort(adjList, new Comparator<int[]>() {	// 가중치 작은 순으로 정렬
			@Override
			public int compare(int[] o1, int[] o2) {
				return o1[2]-o2[2];
			}
    	});
    	
    	int answer = 0, count = n;
    	for(int[] arr : adjList) {
    		if(union(arr[0], arr[1])) {
    			answer += arr[2];
    			count--;
    		}
    		if(count == 0) break;
    	}
    	
        return answer;
    }
    
    public static int find(int a) {
    	if(parents[a] == a) return a;
    	return parents[a] = find(parents[a]);
    }
    
    public static boolean union(int a, int b) {
    	int aRoot = find(a);
    	int bRoot = find(b);
    	if(aRoot == bRoot) return false;
    	
    	parents[bRoot] = aRoot;
    	return true;
    }
    
    
    static int N;
    static int[] parents;
    public static void makeSet() {
    	parents = new int[N];
    	for (int i = 0; i < N; i++) {
			parents[i] = i;
		}
    }
}