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

문제

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

코딩테스트 연습 - 섬 연결하기

섬 연결하기

풀이

MST 만드는 문제로 보여서 크루스컬 알고리즘으로 풀었다.

가중치가 적은 간선부터 사이클이 만들어지지 않을 경우, 연결해 나간다.

 

소스코드

import java.util.*; 

class Edge implements Comparable<Edge>{
    int nodeA;
    int nodeB;
    int weight;
    
    public Edge(int nodeA, int nodeB, int weight){
        this.nodeA = nodeA;
        this.nodeB = nodeB;
        this.weight = weight;
    }
    
    @Override
    public int compareTo(Edge e){
        return this.weight - e.weight;
    }
}

class Solution {
    public int[] parent;
    public int[] rank;
    public int n;
    public PriorityQueue<Edge> edges;
    public int solution(int n, int[][] costs) {
        this.n = n;
        edges = new PriorityQueue<Edge>();
        for(int i = 0; i < costs.length; i++){
            edges.offer(new Edge(costs[i][0], costs[i][1], costs[i][2]));
        }
        
        int answer = 0;
        
        makeSet();
        while(!edges.isEmpty()){
            Edge e = edges.poll();
            if(find(e.nodeA) != find(e.nodeB)){
                answer += e.weight;
                union(e.nodeA, e.nodeB);
            }
        }
 
        return answer;
    }
    
    private int find(int node){
        if(parent[node] == node) return node;
        return find(parent[node]);
        
    }
    
    private void union(int nodeA, int nodeB){
        nodeA = find(nodeA);
        nodeB = find(nodeB);
        if(rank[nodeA] > rank[nodeB]){
            parent[nodeB] = nodeA;
        } else {
            if(rank[nodeA] == rank[nodeB]){
                rank[nodeB] = rank[nodeB] + 1;
            }
            parent[nodeA] = nodeB;
        }
    }
    
    private void makeSet(){
        parent = new int[n];
        rank = new int[n];
        for(int i = 0; i < n; i++ ){
            parent[i] = i;
            rank[i] = 0;
        }
    }
}