코딩테스트 연습 탐욕법(Greedy) 섬 연결하기 JAVA

1. 메인 메서드 

	public int solution(int n , int[][] costs){
    
    	int answer = 0;
        
        //cost 오름차순 정렬 
        Arrays.sort(costs,(o1,o2 -> o1[2] - o2[2]);
        
        //부모 노드 초기화 
        int[] parent = new int[n]; 
        for(int i=0; i<parent.length; i++) {
        	parent[i] = i;
        }
        
        answer = kruskal(costs, parent);
        return answer;
    }

 

2. 크루스칼 메서드

public static int kruskal(int[][] costs, int[] parent){

	int cost = 0; 
    
    for(int i = 0; i < costs.length; i++) {
    
    	//첫번째 섬과 두번째 섬의 부모가 다를 때 
    	if(find(parent, costs[i][0]) != find(parent, costs[i][1])){
        	cost += costs[i][2];
            union(parent, costs[i][0], costs[i][1]);
        }
    
    }

	return cost;
    
}

 

3. x의 부모를 찾는 find 메서드

public static int find(int[] parent , int x){

	if(parent[x] == x) return x;
    else return find(parent, parent[x]);

}

 

4. x와 y그래프를 합치는 union 메서드

public static void union(int[] parent, int x, int y){
	x = find(parent, x); //부모 노드 찾기?
    y = find(parent, y);
    if(x < y) parent[y] = x;
    else parent[x] = y;
}

 

노드 번호가 작은 쪽이 부모가 되도록 한다.

 

---

최종 코드

import java.util.*;

class Solution {

	public int solution(int n, int[][] costs){
    
    	int answer = 0;
        
        //costs 의 비용 부분 기준으로 오름차순 정렬
        Arrays.sort(costs, (o1,o2) -> o1[2] - o2[2]);
        
        //부모 노드 초기화 
        int[] parent = new int[n+1];
        
        for(int i=0; i < parent.length ; i++) {
        	parent[i] = i;
        }
        
        answer = kruskal(costs, parent);
        return answer;
    }
    
    public static int kruskal(int[][] costs, int[] parent){
    
    	int cost = 0;
        
        for(int i = 0; i < costs.length; i++) {
        	
            if(find(parent, costs[i][0]) != find(parent, costs[i][1])){
            	cost += costs[i][2];
                union(parent, costs[i][0], costs[i][1]);
            }
        }
        
        return cost;
    
    }
    
    public static int find(int[] parent, int x){
    	if(parent[x] == x) return x;
        else return find(parent, parent[x]);
    }

	public static void union(int[] parent, int x, int y){
    	x = find(parent, x);
        y = find(parent, y);
        if( x<y ) parent[y] = x;
        else parent[x] = y;
    }
    
}

 

---

진짜 정리 잘했다고 느꼈던 참고한 블로그 : 

 

https://velog.io/@suk13574/%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98Java-%EC%9C%A0%EB%8B%88%EC%98%A8-%ED%8C%8C%EC%9D%B8%EB%93%9CUnion-Find-%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98

[알고리즘/Java] 유니온 파인드(Union-Find) 알고리즘