프로그래머스(섬 연결하기)

import java.util.*;

class Bridge implements Comparable<Bridge>{
    int cost;
    int from;
    int to;
    public Bridge(int cost, int from, int to) {
        this.cost = cost;
        if(from < to) {
            this.from = from;
            this.to = to;
        }
        else {
            this.from = to;
            this.to = from;  
        }
    }
    @Override
    public int compareTo(Bridge b) {
        if(b.cost < cost)
            return 1;
        else if(cost < b.cost)
            return -1;
        else
            return 0;
    }
}
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;
        
        List<Bridge> list = new ArrayList<>();
        
        for(int[] cost : costs)
            list.add(new Bridge(cost[2], cost[0], cost[1]));
        
        Collections.sort(list);
        
        for(Bridge bridge : list) {
            if(!isSameParent(bridge.from, bridge.to)) {
                answer += bridge.cost;
                setParent(bridge.from, bridge.to);
            }
        }
        return answer;
    }
    public boolean isSameParent(int i, int j) {
        if(getParent(i) != getParent(j))
            return false;
        return true;
    }
    public int getParent(int i) {
        if(parent[i] != i) {
            return getParent(parent[i]);
        }
        return parent[i];
    }
    public void setParent(int i, int j) {
        if(getParent(i) != i) {
            parent[getParent(j)] = getParent(i);
        } 
        else if(getParent(j) != j) {
            parent[getParent(i)]  = getParent(j);
        }
        else {
            parent[j] = parent[i];
        }
    }
}

크루스칼 알고리즘을 써야 하는 문제이다.

처음 봤을 때는 억... 했지만 크루스칼 알고리즘을 다시 복기하고 나니까 크게 어려운 문제는 아니었다.

크루스칼 알고리즘을 써야하는 문제는 이렇게 생겼구나 하고 기억만 해두면 문제는 없을 것 같다.

까먹지 말아야 할 건 setParent에서 parent[j] = ~~~~가 아니라 parent[getParent(j)] = ~~~~~가 되야 한다는 점.

서로 다른 그룹을 연결하기 위해서는 최상위 부모가 되는 노드끼리 연결을 해주어야 하기 때문.

스터디 공부 하고 관련 문제를 풀어봤는데 재미는 있는데... 이거에 시간 쓸 때가 아닌데 어휴