문제

https://school.programmers.co.kr/learn/courses/30/lessons/42861

풀이 방법

최소 비용으로 모든 정점을 연결해야 하는 문제다.

• 간선 비용을 기준으로 오름차순 정렬한다.

Arrays.sort(costs, new Comparator<int[]>(){
        
            @Override
            public int compare(int[] o1, int[] o2){
                return o1[2] - o2[2];
            }
        });

• 모든 간선을 탐색하며 union을 만든다.

for(int i = 0; i < costs.length; i++){
            int vtx1 = costs[i][0];
            int vtx2 = costs[i][1];
            
            if(union(vtx1, vtx2)){
                totalVal += costs[i][2];
            }
        }

모든 그래프가 연결되어 하나의 union이 되면 모든 정점의 root는 같다.

union-find 알고리즘

두 노드가 같은 그래프에 속하는지 확인하는 알고리즘이다.
크게 find, union 두 동작이 있다.

• find : 해당 그래프의 루트를 찾는다

public static int find(int x){
    if(parent[x] == x) return x;
        else return find(parent[x]);
}

• union : 그래프로 만든다

public static boolean union(int x, int y){
    int xParent = find(x);
    int yParent = find(y);
//        
    if(xParent == yParent) return false;      //이미 같은 유니온
//        
    // 작은 것이 부모가 됨 
    if(xParent < yParent) parent[yParent] = xParent;
    else parent[xParent] = yParent;
//        
    return true;
}

코드

import java.util.*;
// 간선 비용 기준으로 정렬하고, union에 포함된 것인지 확인해서 포함 안됐으면 해당 간선 추가 
// 유니온 파인드로 해결하기 
class Solution {
    
    public static int[] parent;
    
    // 루트를 찾는 함수 
    public static int find(int x){
        if(parent[x] == x) return x;
        else return find(parent[x]);
    }
    
    //유니온을 만드는 함수 
    public static boolean union(int x, int y){
        int xParent = find(x);
        int yParent = find(y);
        
        if(xParent == yParent) return false;      //이미 같은 유니온
        
        // 작은 것이 부모가 됨 
        if(xParent < yParent) parent[yParent] = xParent;
        else parent[xParent] = yParent;
        
        return true;
    }
    
    public int solution(int n, int[][] costs) {
        int answer = 0;
        int totalVal = 0;
        parent = new int[n];
        
        for(int i = 0; i < n; i++){
            parent[i] = i;
        }
        
        // 간선 비용 기준 정렬 
        Arrays.sort(costs, new Comparator<int[]>(){
        
            @Override
            public int compare(int[] o1, int[] o2){
                return o1[2] - o2[2];
            }
        });
        
        
        for(int i = 0; i < costs.length; i++){
            int vtx1 = costs[i][0];
            int vtx2 = costs[i][1];
            
            if(union(vtx1, vtx2)){
                totalVal += costs[i][2];
            }
        }
        
        answer = totalVal;
        
        return answer;
    }
}