[99클럽 코테 스터디 8일차 TIL] 그리디

📖 오늘의 학습 키워드
그리디(크루스칼 알고리즘)

오늘의 회고

문제

[섬 연결하기]
https://school.programmers.co.kr/learn/courses/30/lessons/42861

나의 해결

import java.util.*;
class Solution {
    public int[] parents;
    public int solution(int n, int[][] costs) {
        int answer = 0;
        parents = new int[n];
        for(int i = 0; i < n; i++) {
            parents[i] = i;
        }
        Arrays.sort(costs, (a, b) -> a[2] - b[2]);
        for(int i = 0; i < costs.length; i++) {
            if(union(costs[i][0], costs[i][1])){
                answer += costs[i][2];
            }
        }
        return answer;
    }
    public boolean union(int a, int b){
        int aParent = find(a);
        int bParent = find(b);
        if(aParent == bParent) {
            return false;
        }
        if(aParent < bParent) {
            parents[bParent] = aParent;
        } 
        else {
            parents[aParent] = bParent;
        }
        return true;
    }
    public int find(int n) {
        if(parents[n] == n) {
            return n;
        }
        return parents[n] = find(parents[n]);
    }
}

전에 Union-Find 알고리즘을 공부하면서 풀어보았던 백준의 전력난([백준] 6497 : 전력난) 문제가 떠올라서 어렵지 않게 풀 수 있었다.

1. parents 배열로 해당 섬 부모의 값을 나타낸다.
   • 처음에는 각 섬의 부모가 자기 자신이 되도록 초기화한다.
2. 다리를 건설하는 비용이 적은 순으로 costs 배열을 정렬한다.
3. costs 배열을 순회하며 연결할 두 섬의 부모가 같은지 확인한다.
   • 부모가 같으면 해당 다리는 건설하지 않는다.
   • 부모가 다르면 해당 다리를 건설하고 answer에 건설 비용을 더한다.

새로 학습한 내용

오랜만에 크루스칼 알고리즘을 복습할 수 있었다.