Solution.java

import java.util.*;

class Solution {
    int[] p;
    
    public int solution(int n, int[][] costs) {
        int answer = 0;
        
        p = new int[n];
        
        for (int i = 0; i < n; i++) p[i] = i;
        
        Arrays.sort(costs, Comparator.comparingInt(o -> o[2]));
        
        for (int[] cost : costs) {
            int a = find(cost[0]);
            int b = find(cost[1]);
            
            if (a != b) {
                union(a, b);
                answer += cost[2];
            }
        }
        
        return answer;
    }
    
    int find(int child) {
        if (p[child] == child) return child;
        
        return p[child] = find(p[child]);
    }
    
    void union(int a, int b) {
        p[b] = a;
    }
}

최소 신장 트리 문제였다. union-find 알고리즘을 구현하여 해결했다.

출처: 프로그래머스 코딩 테스트 연습, https://programmers.co.kr/learn/challenges