[프로그래머스][섬 연결하기]-Lv.3

🧨 문제

문제링크

🧨 제한사항

🧨 접근방법

1. 크루스칼 알고리즘으로 Union & Find를 사용하였다.
2. 같은 부모일 경우 continue를 통해서 Union을 하지않는다.
   -> Union을 할 경우 사이클이 생기므로 안된다.

🧨 코드

import java.util.*;
class Solution {
    static int[] group;
    public int solution(int n, int[][] costs) {
        int answer = 0;
        group = new int[n];
        // 그룹 초기화
        for(int i=0; i<n; i++){
            group[i] = i;
        }
        Arrays.sort(costs, (o1,o2)-> Integer.compare(o1[2],o2[2]));
        for(int i=0; i<costs.length; i++){
            int a = find(costs[i][0]);
            int b = find(costs[i][1]);
            int cost = costs[i][2];
            
            if(a == b) continue;
            union(a,b);
            answer += cost;
        }
        return answer;
    }
    public int find(int x){
        if(group[x] == x){
            return x;
        }
        return group[x]=find(group[x]);
    }
    public void union(int a, int b){
        int groupA = find(a);
        int groupB = find(b);
        
        if(groupA > groupB){
            group[groupA] = groupB;
        }else{
            group[groupB] = groupA;
        }
    } 
}

참고

https://velog.io/@qodlstjd12/%ED%94%84%EB%A1%9C%EA%B7%B8%EB%9E%98%EB%A8%B8%EC%8A%A4-%EC%84%AC-%EC%97%B0%EA%B2%B0%ED%95%98%EA%B8%B0-Java