[프로그래머스] 섬 연결하기 Java 풀이 및 해설

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

프로그래머스

풀이 방법

싸이클이 없이 최소 비용으로 모든 노드를 연결하는 최소 비용 신장 트리를 구하면 된다.

최소 비용 신장 트리를 구하기 위한 알고리즘으로 크루스칼을 사용하였다.

여기에 Union-Find 알고리즘도 사용된다.

 

처음에 DFS로 최소 비용 신장 트리를 구하면 되는게 아닌가 싶었는데

DFS는 한 노드에 하나의 노드만 연결되게(진행 방향으로만) 탐색하기에 아래의 그림을 예로

0번 노드에서 1과 2번 노드가 연결된 상황이 나올 수가 없다..

 

전체 코드

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