문제

문제 링크

접근

• 여러 개의 간선을 지나고, 모든 정점을 방문해야 한다는 점에서 MST(최소 신장 트리)를 떠올렸다.
• MST 풀이 알고리즘으로는 대표적으로 크루스칼, 프림이 있다.
• 그 중 나는 우선순위큐, union-find를 이용하는 프림을 채택하였다.
• 프로그래머스 level3 치고는 전형적이고 쉬운 문제 같다.

소스 코드

import java.util.*;

class Solution {
    int[] parent;
    Queue<Edge> q = new PriorityQueue<>();
    public int solution(int n, int[][] costs) {
        int answer = 0;
        parent = new int[n];
        int cnt = 0;
        
        for (int i = 1; i < n; i++) parent[i] = i;
        for (int[] cost : costs) q.add(new Edge(cost));
        
        while(!q.isEmpty() && cnt < n - 1) {
            Edge e = q.poll();
            
            if(!union(e.start, e.end)) continue;
            cnt++;
            answer += e.cost;
        }
        
        return answer;
    }
    
    private boolean union(int a, int b) {
        int pa = find(a);
        int pb = find(b);
        
        if (pa == pb) return false;
        parent[pa] = pb;
        return true;
    }
    
    private int find(int v) {
        if (v == parent[v]) return v;
        return parent[v] = find(parent[v]);
    }
    
    
    class Edge implements Comparable<Edge> {
        int start, end, cost;
        
        public Edge(int[] cost) {
            this.start = cost[0];
            this.end = cost[1];
            this.cost = cost[2];
        }
        
        @Override
        public int compareTo(Edge e) {
            return this.cost - e.cost;
        }
    }
}