프로그래머스 - 섬연결하기

위에 그림 처럼 구조가 될 것이다. paraent배열에 들어있는건 부모 노드의 번호가 된다. 이 기준으로 find를 한다면 부모 노드를 통해서 구해지기에 이걸 통해서 비교를 해주고 이미 지나간 것은 동일하기에 최소 값을 기준으로 구할 수 있다. 

 

해당 문제는 신장트리 , 크루스칼 알고리즘 , 유니온 - 파인드 알고리즘을 통해서 구했다. 

import java.util.*;

class Solution {
    private int[] parent;
    public int find(int a) {
        if(parent[a]==a) return a;
        else return parent[a] = find(parent[a]);
    }
    
    public void union(int a, int b) {
        a = find(a);
        b = find(b);
        if(a != b) {
            parent[b] = a;
        }
    }
    
    public int solution(int n, int[][] costs) {
        int answer = 0;
        parent = new int[n];
        for(int i=0; i<n; i++) {
            parent[i] = i;
        }
        
        Arrays.sort(costs, (o1, o2) -> o1[2] - o2[2]);
        
        for(int i=0; i< costs.length; i++) {
            if(find(costs[i][0]) != find(costs[i][1])) {
                union(costs[i][0], costs[i][1]);
                answer += costs[i][2];
            }
        }
        
        return answer;
    }
}