99클럽 코테 스터디 16일차 TIL - MST (프로그래머스 '섬 연결하기')

항해99 코테 스터디 16일차 문제인 프로그래머스의 '섬 연결하기'는 섬들을 모두 연결하기 위해 필요한 다리들의 최소 비용을 구하는 문제다. 난이도는 레벨3이며 최소신장트리 알고리즘을 통해 해결할 수 있다.

 

오늘의 문제 - 섬 연결하기 문제 정보

문제 키워드

- Greedy, MST

난이도

- Level 3

 

문제 요약

• 섬을 연결하기 위한 다리의 건설 비용 배열이 주어진다.
• 모든 섬이 연결되기 위해 지어야 하는 다리들의 최소 건설 비용을 구하여라.

 

문제 풀이 과정  

• 그래프에서 모든 노드를 연결하는 최소 비용의 간선트리를 '최소신장트리(MST)'라고 한다.
• 최소 신장 트리를 구하는 알고리즘 중 하나인 크루스칼 알고리즘을 이용해 문제를 풀었다.
• 크루스칼 알고리즘은 엣지 리스트를 기반으로 트리를 병합해가므로, 먼저 주어진 비용 리스트를 비용 오름차순으로 정렬하였다.
• 또한 연결 시 사이클 발생 유무 판별을 위해 유니온 파인드 알고리즘을 활용하였다.
• 가장 가중치가 작은 간선부터 하나씩 연결해가며, 사이클이 발생하지 않게 모든 노드를 연결하는 과정을 거쳤다.

[알고리즘] 그래프 문제에 활용되는 유니온 파인드(union-find)

 

 

코드

import java.util.*;

class Solution {
    public int solution(int n, int[][] costs) {
        
        // 엣지 리스트를 가중치 오름차순으로 정렬
        Arrays.sort(costs, new Comparator<int[]>(){
            @Override
            public int compare(int[] o1, int[] o2) {
                return o1[2] - o2[2];
            }
        });
        
        // 유니온 파인드 배열 초기화
        int[] uf = new int[n];
        for(int i=0; i<n; i++) {
            uf[i] = i;
        }
        
        int edgeCnt = 0;
        int answer = 0;
        
        // 최소 엣지부터 연결
        // 연결 시 사이클이 생기는 경우 연결 안함
        for(int[] edge: costs) {
            int s = edge[0], d = edge[1], cost = edge[2];
            if(find(uf, s) != find(uf, d)) {
                union(uf, s, d);
                edgeCnt++;
                answer += cost;
            }
            
            if(edgeCnt == n-1) {
                break;
            }
        }
        
        return answer;
    }
    
    // 노드 b의 대표노드를 노드 a의 대표노드로 변경
    private void union(int[] arr, int a, int b) {
        arr[find(arr, b)] = find(arr, a);
    }
    
    // node의 대표노드를 반환
    // 대표노드를 구하는 과정에서 그 경로에 있는 노드들의 대표노드도 업데이트
    private int find(int[] arr, int node) {
        if(arr[node] != node) {
            return arr[node] = find(arr, arr[node]);
        }
        return arr[node];
    }
}

• 시간복잡도: O(NlogN)
• 공간복잡도: O(N)

 

오늘의 학습 회고

새롭게 알게된 것

• 문제 키워드가 그리디라서 일단 짧은 간선을 먼저 연결해야겠다는 생각은 했는데, 잘 고민해보니 결국 MST를 구하는 문제였다. MST 구하는 알고리즘도 결국 그리디라는 점을 기억해야겠다.