[프로그래머스/JAVA] 섬 연결하기 - Level 3

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

 

 

• 풀이

최소 비용으로 모든 노드를 연결해야 하는 문제입니다.

 

최소 신장 트리 알고리즘인 크루스칼 알고리즘을 사용했습니다.

 

동작 과정

1. 비용이 적은 순으로 정렬을 합니다. (비용이 적은 순으로 먼저 연결해야 최소 비용으로 모든 노드를 가장 먼저 연결할 수 있다.)

2. parent 인덱스를 자신의 인덱스로 설정.

3. 우선순위 큐에 남아있는 cost가 가장 적은 노드먼저 연결을 시도합니다.

4. 부모 인덱스가 start와 end가 같다면 아무런 작업도 하지 않습니다.

5. 부모 인덱스가 다르다면 서로 연결이 되어있지 않기 때문에 연결을 해줍니다.

6. 위의 3~5를 반복합니다.

 

• 코드

 

import java.util.*;

class Solution {
    static int[] parent;
    
    public int solution(int n, int[][] costs) {
        int answer = 0;
        parent = new int[n+1];
        PriorityQueue<Node> node = new PriorityQueue<>();
        for(int i = 0 ; i < costs.length; i++){
            node.add(new Node(costs[i][0], costs[i][1], costs[i][2]));
        }
        
        for(int i = 0 ; i < n ; i++) parent[i] = i;
        
        while(!node.isEmpty()) {
        	Node temp = node.poll();
        	
            if(find(temp.start) == find(temp.end)) continue;
            
            union(temp.start, temp.end);
            answer += temp.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;
    }
}

class Node implements Comparable<Node> {
    int start;
    int end;
    int cost;
    
    public Node(int start, int end, int cost) {
        this.start = start;
        this.end = end;
        this.cost = cost;
            
    }
    
    @Override
    public int compareTo(Node node){
        return this.cost - node.cost;
    }
}