프로그래머스 섬 연결하기

문제

풀이

크루스칼 알고리즘을 통해 MST(최소신장트리)를 구했다. 유니온 파인드를 통해 사이클을 판별했다.

---

코드

import java.util.*;
class Solution {
    static PriorityQueue<Edge> pq;
    static int[] root;
    static int cnt;
    public static int solution(int n, int[][] costs) {
        int answer = 0;
        pq=new PriorityQueue<>();
        for(int[] arr:costs){
            pq.add(new Edge(arr[0],arr[1],arr[2]));
        }
        root = new int[n];
        for(int i=1;i<n;i++)root[i]=i;
        cnt= n;
        while(!pq.isEmpty()){
            if(cnt==1)break;
            Edge edge=pq.poll();
            if(union(edge.from, edge.to))answer+= edge.cost;
        }

        return answer;
    }

    static int find(int x){
        if(x!=root[x]){
            root[x]=find(root[x]);
        }
        return root[x];
    }

    static boolean union(int a,int b){
        a=find(a);
        b=find(b);
        if(a==b)return false;
        if(a<b)root[b]=a;
        else root[a]=b;
        cnt--;
        return true;
    }

    static class Edge implements Comparable<Edge>{
        int from,to,cost;

        public Edge(int from,int to, int cost) {
            this.to = to;
            this.cost = cost;
            this.from=from;
        }

        @Override
        public int compareTo(Edge o) {
            return this.cost-o.cost;
        }
    }
}

#MST #union-find #크루스칼