[프로그래머스] 섬 연결하기 (Java)

프로그래머스 섬 연결하기

문제풀이

모든 간선의 비용이 주어지고 가장 적은 비용으로 모든 정점을 연결하는 문제는 MST의 개념 그 자체를 나타내는 문제다. 이 문제는 크루스칼 알고리즘을 이용하여 풀었다.

• 주어진 모든 간선을 비용을 기준으로 오름차순 정렬한다.
• 하나씩 간선을 꺼내어 싸이클이 만들어지지 않는 선에서 연결한다.
  • union-find 알고리즘이 사용된다. 반드시 숙지하자!

구현코드

import java.util.*;

class Solution {
    class Edge implements Comparable<Edge> {
        int from, to, cost;
        
        Edge(int from, int to, int cost){
            this.from = from;
            this.to = to;
            this.cost = cost;
        }
        
        @Override
        public int compareTo(Edge o){
            return this.cost - o.cost;
        }
    }
    
    static int[] parent;
    static PriorityQueue<Edge> adj;
    
    public int solution(int n, int[][] costs) {
        int answer = 0;
        parent = new int[n];
        adj = new PriorityQueue<>();
        
        for(int i = 0 ; i < costs.length ; ++i){
            Edge edge = new Edge(costs[i][0], costs[i][1], costs[i][2]);
            adj.offer(edge);
        }
        
        for(int i = 0 ; i < n ; ++i) parent[i] = i;
        
        while(!adj.isEmpty()) {
        	Edge edge = adj.poll();
        	
            if(find(edge.from) == find(edge.to)) continue;
            else {
                union(edge.from, edge.to);
                answer += edge.cost;    
            }
        }
        
        return answer;
    }
    
    public int find(int n){
        if(parent[n] == n) return n;
        return parent[n] = find(parent[n]);
    }
    
    public void union(int a, int b){
        int rootA = find(a);
        int rootB = find(b);
        
       if(rootA != rootB) parent[rootB] = rootA;
    }
}