프로그래머스 - 섬 연결하기 - MST - Java

1. 문제

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

참고 풀이

2-1. 크루스칼 풀이

크루스칼은 정렬 후 UnionFind를 통해 찾는 것이 가장 중요하다.

3-1. 크루스칼 코드

import java.util.*;
class Solution {
    int[] parent;
    
    public int solution(int n, int[][] costs) {
        int answer = 0;
        
        parent = new int[n];
        for(int i = 0; i < n; i++)
            parent[i] = i;
        
        Arrays.sort(costs, (o1, o2) -> o1[2] - o2[2]);
        
        for(int i = 0; i < costs.length; i++){
            int a = costs[i][0];
            int b = costs[i][1];
            int cost = costs[i][2];
            
            if(findParent(a) != findParent(b)){
                union(a, b);
                answer += cost;
            }
        }
        return answer;
    }
    
    public int findParent(int x){
        if(x == parent[x]) return x;
        else return parent[x] = findParent(parent[x]);
    }
    
    public void union(int a, int b){
        a = findParent(a);
        b = findParent(b);
        
        if(a < b){
            parent[b] = a;
        } else{
            parent[a] = b;
        }
    }
}

---

2-2. 프림 풀이

1. 간선의 정보를 ArrayList<>에 저장한다. 이때 양방향이므로 양쪽에 다 저장한다.

2. (문제에서 시작노드가 주어지지 않는다면 임의로 시작노드를 정해서) 시작노드가 visit되었는지 파악하고, 아니라면 visit처리 후 연결비용을 더한다.

3. PriorityQueue에서 제일 작은 값을 꺼내서 더하고, 이 노드와 연결된 다른 점들을 방문이 되어 있지 않다면 PriorityQueue에 넣어준다.

2-3. 프림 코드

import java.util.*;

class Solution {
    public int solution(int n, int[][] costs) {
        PriorityQueue<Edge> pq = new PriorityQueue<>();
        boolean visit[] = new boolean[n];
        int answer = 0;
        
        ArrayList<ArrayList<Edge>> list = new ArrayList<>();
        for(int i = 0; i < n; i++){
            list.add(new ArrayList<>());
        }
        
        for(int i = 0; i < costs.length; i++){
            int v = costs[i][0];
            int w = costs[i][1];
            
            list.get(v).add(new Edge(w, costs[i][2]));
            list.get(w).add(new Edge(v, costs[i][2]));
        }
        
        pq.add(new Edge(0, 0));
        while(!pq.isEmpty()){
            Edge edge = pq.poll();
            
            if(visit[edge.node]) continue;
            
            visit[edge.node] = true;
            
            answer += edge.cost;
            for(Edge e : list.get(edge.node)){
                if(!visit[e.node]){
                    //System.out.println(edge.node + " " + e.node + " " + e.cost);
                    pq.add(new Edge(e.node, e.cost));
                }
            }
        }
        
        return answer;
    }
    
    public class Edge implements Comparable<Edge> {
        int node;
        int cost;
        
        public Edge(int node, int cost){
            this.node = node;
            this.cost = cost;            
        }
        
        @Override
        public int compareTo(Edge other){
            return Integer.compare(this.cost, other.cost);
        }
    }
}