99클럽 코테 스터디 20일차 TIL / [프로그래머스] 섬 연결하기

오늘의 학습 키워드

---

MST, 크루스칼 알고리즘

문제

---

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

• 플랫폼: 프로그래머스
• 문제명: 섬 연결하기
• 난이도: Lv3

풀이

---

import java.util.*;

class Solution {
    
    static int[] parent;
    
    public int solution(int n, int[][] costs) {
        parent = new int[n];
        int answer = 0;
        
        for(int i=0; i<n; i++) {
            parent[i] = i;
        }
        
        Arrays.sort(costs, (o1, o2) -> { 
            return o1[2] - o2[2];
        });
        
        for(int[] cost : costs) {
            if(find(cost[0]) != find(cost[1])) {
                union(cost[0], cost[1]);
                answer += cost[2];
            }
        }
        
        return answer;
    }
    
    public void union(int x, int y) {
        x = find(x);
        y = find(y);
        
        if(x != y) {
            if(x <= y) {
                parent[y] = x;
            } else {
                parent[x] = y;
            }
        }
    }
    
    public int find(int x) {
        if(parent[x] == x) {
            return x;
        }
        
        return parent[x] = find(parent[x]);
    }
}

접근

• 이 문제는 최소 신장 트리를 구하는 문제입니다. 연결되지 않는 경우는 없다고 문제에 정의되어 있으니, 고려하지 않아도 됩니다.
• 최소 신장 트리를 구하는 대표적인 알고리즘인 크루스칼 알고리즘을 사용했습니다.
• 주어진 costs 배열을 비용에 따라 오름차순 정렬을 수행한 뒤, 순서대로 순회하며 다리를 연결합니다.
  • 이때, 사이클이 형성되지 않도록 해야합니다.
    • 사이클 존재 여부는 union-find 알고리즘을 통해 판단했습니다.

소요 시간

1시간