Algorithm - 프로그래머스 섬 연결하기(Greedy, Minimum Spanning Tree, Union Find)

 

 

프로그래머스

 

이 문제를 해결하기 위해 생각했던 방법은

1. 주어진 배열을 다리를 짓는데에 필요한 재화(costs[i][2])로 오름차순 정렬

2. 섬이 직접적으로 연결되어 있는지 확인

3. 직접 연결되어 있지 않다면 간접적으로 연결되어 있는지 확인(dfs, bfs 등 사용)

4. 간접적으로 연결되어 있지 않다면 다리 건설

 

이렇게 해결하려 하였으나, 3번을 구현하는데에 어려움을 겪어 해결방안을 찾아보았다.

 

Minimum Spanning Tree(최소 신장 트리), Kruskal(크루스칼) 알고리즘, Union Find

이 세가지 개념으로 해결하는 문제였었다.

 

최소 신장 트리(MST; Minimum Spanning Tree)

Spannig Tree 중 사용된 간선(다리)들의 가중치 합(다리 건설 가격)이 최소인 트리

 

Spanning Tree

• 최소의 간선으로 그래프 내의 모든 정점을 연결하는 트리
• 사이클을 이루어서는 안된다
• 다리의 수(간선의 수)는 섬의 수(n) - 1개일 경우 Spanning Tree를 만족하게된다. 
• 하나의 그래프에는 많은 신장 트리가 존재할 수 있다.

 

 

Kruskal 알고리즘

 

MST를 구하기 위한 알고리즘

greedy를 이용하여 가중치를 간선에 할당한 그래프(다리 및 다리 비용)의 모든 정점을 최소 비용으로 연결하는 알고리즘

 

과정

1. 그래프 간선들을 가중치의 오름차순으로 정렬

2. 정렬된 간선 리스트에서 순서대로 사이클을 형성하지 않는 간선을 선택

3. 해당 간선을 현재의 MST의 집합에 추가한다.

 

 

 

Prim 알고리즘

시작 정점에서부터 출발하여 신장트리 집합을 단계적으로 확장해나가는 방법

 

과정

1. 시작 단계에서는 시작 정점만이 MST 집합에 포함된다.

2. 앞 단계에서 만들어진 MST 집합에 인접한 정점들 중에서 최소 간선으로 연결된 정점을 선택하여 트리를 확장한다

3. 위 과정을 트리가 N-1개의 간선을 가질 때 까지 반복한다.

 

 

합집합 찾기(Union Find)

서로소 집합(Disjoint Set) 알고리즘 이라고도 불리며, 그래프의 연결성을 확인하거나 사이클을 찾는 데 사용된다.
주어진 노드의 부모를 찾는다.

여러개의 노드가 존재할 때, 두개의 노드를 선택하여 서로 같은 그래프에 속하는지 판별하는 알고리즘이다.

 

 

17. Union-Find(합집합 찾기)

 

 

 

해결코드

import java.util.*;

public class Main {
    static int[] parent;

    public static void main(String[] args) {
        int n = 4;
        //a번째 섬과 b번째 섬을 연결하기 위해 c원이 필요
        int[][] costs = {{0,1,1}, {0,2,2}, {1,2,5}, {1,3,1}, {2,3,8}};

        int answer = 0;
        
        // Kruskal 알고리즘을 사용하기 위해 비용을 기준으로 간선을 오름차순으로 정렬
        Arrays.sort(costs, Comparator.comparingInt(arr -> arr[2]));
        
        parent = new int[n];
        
        // 각 노드의 부모를 자기 자신으로 초기화
        for (int i = 0; i < n; i++) {
            parent[i] = i;
        }
        
        // 간선을 하나씩 확인하며 사이클을 형성하지 않는 간선을 선택
        for(int[] cost: costs){
            int fromParent = findParent(cost[0]);
            int toParent = findParent(cost[1]);

            // 두 노드가 같은 집합에 속하지 않으면 연결하고 비용을 더함
            if(fromParent != toParent) {
                answer += cost[2];
                parent[toParent] = fromParent;
            }
        }
        
        // 최소 비용 출력
        System.out.println(answer);
    }

    // Union-Find(노드의 부모를 찾는 함수)
    private static int findParent(int from) {
        if(parent[from] == from) return from;
        return parent[from] = findParent(parent[from]);
    }
}

 

 

처음에는 정렬 후 dfs, bfs를 통하여 해결하는 문제인줄 알았으나,

찾아보니 Kruskal 알고리즘과 UnionFind를 통하여 해결하여야 하는 문제였다.

혼자 힘으로 풀진 못했지만, 풀이와 생각했던 방법이 방향이 일치하여 나름 기뻤다.

오늘 문제로 덕에 여러 알고리즘을 알게되었다. 능숙하게 사용할 수 있도록 비슷한 문제를 더 풀어야겠다.

 

 

 

 

참조 블로그: