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

문제 접근

문제를 읽자마자 최소신장트리를 구하라는 것을 이론적으로는 알았다. 그래서 프림과 크루스칼 중 구현이 쉬운걸로 기억하는 크루스칼을 선택했다.
그래서 코드를 구현했는데 내가 기억을 잘못해서 Union-Find가 빠진 다음과 같은 크루스칼 알고리즘을 구현했다.
때문에, 그래프가 연결되는 과정에서 독립된 그래프들을 이어줄 수 없게 되었다. 즉, 두 노드의 처리여부뿐 아니라 두 노드가 같은 그래프(=집합)에 속하는지도 판단해야한다.
이를 위해, 각 집합에서 항상 루트 노드만을 가리키는 테이블을 유지해서 동일 집합인지 판단할 수 있는 Union-Find를 추가적용했다.

import java.util.*;
import java.io.*;

class Solution {
    public int solution(int n, int[][] costs) {
        boolean[] isVisited = new boolean[n];
        
        int answer = 0;
        PriorityQueue<Edge> pq = new PriorityQueue<Edge>((e1, e2)->{
            return e1.cost - e2.cost;
        });
        for(int i=0; i<costs.length; i++) {
            pq.add(new Edge(costs[i][0], costs[i][1], costs[i][2]));
        }
        
        int count = 0;
        while(!pq.isEmpty()) {
            Edge e = pq.poll();
            
            if(isVisited[e.n1] && isVisited[e.n2]) continue;
            count++;
            answer+=e.cost;
            isVisited[e.n1] = true;
            isVisited[e.n2] = true;
        }
        
        return answer;
    }    
}

class Edge {
    int n1;
    int n2;
    int cost;
    Edge(int n1, int n2, int cost){
        this.n1 = n1;
        this.n2 = n2;
        this.cost = cost;
    }
}

문제 풀이 - Union-Find 추가

import java.util.*;
import java.io.*;

class Solution {
    int[] rootTable;
    public int solution(int n, int[][] costs) {
        boolean[] isVisited = new boolean[n];
        rootTable = new int[n];
        for(int i=0; i<n; i++) rootTable[i] = i; // 자기 자신만 갖는 집합을 구성
        
        int answer = 0;
        PriorityQueue<Edge> pq = new PriorityQueue<Edge>((e1, e2)->{
            return e1.cost - e2.cost;
        });
        for(int i=0; i<costs.length; i++) {
            pq.add(new Edge(costs[i][0], costs[i][1], costs[i][2]));
        }
        
        int count = 0;
        while(!pq.isEmpty()) {
            Edge e = pq.poll();
            
            if(isVisited[e.n1] && isVisited[e.n2] && find(e.n1)==find(e.n2)) continue;
            count++;
            answer+=e.cost;
            
            union(e.n1, e.n2);
            isVisited[e.n1] = true;
            isVisited[e.n2] = true;
        }
        
        return answer;
    }
    
    // 대장끼리 싸워서 이긴쪽(값이 더작은 쪽)이 흡수된다.
    void union(int n1, int n2) {
        if(rootTable[n1] != rootTable[n2]) {
            int n1Parent = find(n1);
            int n2Parent = find(n2);           
            if (n1Parent < n2Parent) {
                rootTable[n2Parent] = n1Parent;
            } else {
                rootTable[n1Parent] = n2Parent;
            }
        }
    }
    
    // 자신의 집합의 대장을 찾아가는 과정. 여기서 테이블을 업데이트한다.
    // 여기서 업데이트 해줘야 다음에 조회시 시간 절약이 가능하다.
    int find(int n) {
        if(rootTable[n] == n) return n;
        int newRoot = find(rootTable[n]);
        rootTable[n] = newRoot;
        return newRoot;
    }
    
}

class Edge {
    int n1;
    int n2;
    int cost;
    Edge(int n1, int n2, int cost){
        this.n1 = n1;
        this.n2 = n2;
        this.cost = cost;
    }
}

이론상으로는 알았으나, 코드로 구현하는 과정에서 실수를 했다. 3년 전 알고리즘 수업 때 과제로 구현했던 적이 분명 있는데도 실수했다... 역시 이론보다는 직접 구현을 많이 해봐야 하는것 같다.