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

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

프로그래머스

 

크루스칼 알고리즘을 알면 바로 풀 수 있는 문제이다.

https://developerwoohyeon.tistory.com/192

신장트리(Spanning Tree), 최소신장 트리(Minimum Spanning Tree)

 

우선 크루스칼 알고리즘을 적용하기 위해서는 간선의 가중치를 기준으로 오름차순으로 정렬해야 한다.

 

Arrays.sort(costs,(a,b)->Integer.compare(a[2],b[2]));

 

 

그 후 find와 union함수를 만들어줘야 한다.

 

find 함수 ==> x가 속한 집합의 대표(루트) 노드를 찾는 역할

 

union 함수 ==> 두 노드가 속한 집합을 하나로 합치는 역할을 한다.

 

private int find(int[] island, int x){
        if(island[x]==x){
            return x;
        }
        return find(island,island[x]);
    }
    
    private void unite(int[] island, int x, int y){
        int a = find(island,x);
        int b = find(island,y);
        
        island[a]=b;
    }

 

 

이제 오름 차순으로 정렬된 입력 배열을 순회하면서 find와 union을 사용하면 된다.

 

하지만 사이클이 존재하면 최소 최소신장트리를 위배하는 것이기 때문에 사이클이 존재하는지를 체크해줘야 한다.

 

여기서는 대표노드가 같으면 사이클이 발생하기 때문에 find 결과가 같은지를 비교해야한다.

for(int i=0; i<costs.length; i++){
            if(find(island, costs[i][0])!=find(island,costs[i][1])){ //대표노드가 같은지 체크
                unite(island,costs[i][0],costs[i][1]);
                answer+=costs[i][2];
            }
        }

 

 

<전체 코드>

import java.util.*;

class Solution {
    public int solution(int n, int[][] costs) {
        int answer = 0;
        int[] island = new int[n];
        
        boolean[] visit = new boolean[n];
        for(int i=0; i<n; i++){
            island[i]=i;    
        }
        
        Arrays.sort(costs,(a,b)->Integer.compare(a[2],b[2]));
        
        for(int i=0; i<costs.length; i++){
            if(find(island, costs[i][0])!=find(island,costs[i][1])){
                unite(island,costs[i][0],costs[i][1]);
                answer+=costs[i][2];
            }
        }
        return answer; 
    }
    
    private int find(int[] island, int x){
        if(island[x]==x){
            return x;
        }
        return find(island,island[x]);
    }
    
    private void unite(int[] island, int x, int y){
        int a = find(island,x);
        int b = find(island,y);
        
        island[a]=b;
    }
}

 

 

참고자료

https://maetdori.tistory.com/entry/%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98-Kruskal-Algorithm-Union-Find-%ED%81%AC%EB%A3%A8%EC%8A%A4%EC%B9%BC-%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98-%EC%9C%A0%EB%8B%88%EC%98%A8-%ED%8C%8C%EC%9D%B8%EB%93%9C

[알고리즘] Kruskal Algorithm, Union Find (크루스칼 알고리즘, 유니온 파인드)