프로그래머스 - 섬 연결하기(Java, LV3) / MST

https://programmers.co.kr/learn/courses/30/lessons/42861?language=java

코딩테스트 연습 - 섬 연결하기

풀이

해당 문제는 graph의 MST(Minimum Spanning Tree) 최소연결간선 트리 찾기 문제로 크루스칼 알고리즘으로 해결 가능하다.

 

먼저, 주어진 전체 costs를 비용 순으로 정렬 후 사이클체크를 하면서 

사이클이 형성되지 않는다면 해당 간선을 연결한다. 연결하면서 두 노드를 union 해준다.

그렇게 전체 costs를 탐색하면서 MST가 구성되었다면 중단하여 지금까지 계산한 비용을 반환한다.

import java.util.*;

class Solution {
    
    // 부모 찾기
    public int get_parent(int[] parent, int a){
        int a_p = a;
        while(parent[a_p] != a_p){
            a_p = parent[a_p];
        }
        return a_p;
    }
    
    // 부모 합치기
    public void union_parent(int[] parent, int a, int b){
        int a_p = get_parent(parent, a);
        int b_p = get_parent(parent, b);
        
        if (a_p <= b_p)
            parent[b_p] = a_p;
        
        else
            parent[a_p] = b_p;
    }
    
    // 싸이클 체크
    public boolean same_parent(int[] parent, int a, int b){
        return ((get_parent(parent, a) == get_parent(parent,b)) ? true : false);
    }
    
    // mst 체크
    public boolean mst_check(int[] visit){
        for(int v : visit)
            if (v==0)
                return false;
        return true;
    }
    
    public int solution(int n, int[][] costs) {
        int answer = 0;
        int[] parent = new int[n];
        int[] visit = new int[n];
        
        // parent 초기화
        for(int i=0; i<n; i++)
            parent[i] = i;
    
        // cost 정렬 (cost 기준 오름차순) return 값 음수 그대로
        Arrays.sort(costs, new Comparator<int[]>(){
            @Override
            public int compare(int[] cost1, int[] cost2){
                return cost1[2] - cost2[2];
            }
        });
        // Arrays.sort(costs, (cost1, cost2) -> cost1[2] - cost2[2]);
        
        // Kruskal
        for(int[] cost : costs){ 
            if(mst_check(visit))
                break;
            
            // 목적지 안간 곳이고 cycle check
            if(same_parent(parent, cost[0],cost[1]) == false ){
                answer+= cost[2]; // 비용 추가
                union_parent(parent, cost[0], cost[1]); // union
            }
        }
        
            
        return answer;
    }
}