[Java][프로그래머스] 42861, 섬 연결하기

 

프로그래머스

 

42861, 섬 연결하기

난이도 : Lv 3️⃣

 

🧀 프로세스

 

문제 설명

n개의 섬 사이에 다리를 건설하는 비용(costs)이 주어질 때, 최소의 비용으로 모든 섬이 서로 통행 가능하도록 만들 때 필요한 최소 비용을 return 하도록 solution을 완성하세요.

다리를 여러 번 건너더라도, 도달할 수만 있으면 통행 가능하다고 봅니다. 예를 들어 A 섬과 B 섬 사이에 다리가 있고, B 섬과 C 섬 사이에 다리가 있으면 A 섬과 C 섬은 서로 통행 가능합니다.

제한사항

섬의 개수 n은 1 이상 100 이하입니다.
costs의 길이는 ((n-1) * n) / 2이하입니다.
임의의 i에 대해, costs[i][0] 와 costs[i] [1]에는 다리가 연결되는 두 섬의 번호가 들어있고, costs[i] [2]에는 이 두 섬을 연결하는 다리를 건설할 때 드는 비용입니다.
같은 연결은 두 번 주어지지 않습니다. 또한 순서가 바뀌더라도 같은 연결로 봅니다. 즉 0과 1 사이를 연결하는 비용이 주어졌을 때, 1과 0의 비용이 주어지지 않습니다.
모든 섬 사이의 다리 건설 비용이 주어지지 않습니다. 이 경우, 두 섬 사이의 건설이 불가능한 것으로 봅니다.
연결할 수 없는 섬은 주어지지 않습니다.

 

🔽 문제풀이

2시간 정도 삽질하고, 다양한 사람의 풀이를 참조해서 문제를 풀었다. 얻어갈 것이 많은 문제인 것 같아서 이번 글을 작성한다. 이 문제는 최소 신장트리 문제이며, 해결법으로는 크루스칼 알고리즘과 프림 알고리즘이 있다.

 

💡Kruskal & Prim

🔻신장 트리

그래프의 모든 정점과 간선의 부분 집합으로 구성되는 트리를 말한다. 사이클이 안 생기는 조건 안에서 간선의 개수를 정점 -1개로 골라 만드는 것으로, 정점 -1의 수가 간선의 수가 되는 트리이다.

 

🔻최소 비용 신장 트리(Minimum spanning tree, MST)

신장 트리 중에서 간선들의 합이 최소인 트리를 말한다. 또한 무향 가중 그래프에서 만들어질 수 있고 사이클이 발생되지 않으며, 비용의 합이 최소인 트리이다.

 

🔻최소 비용 신장 트리의 특징

1. 무방향 가중치 그래프.

2. 가중치의 합이 최소.

3. 정점 n개에서 n - 1 개의 간선을 가지는 트리이다.

4. 사이클이 포함되서는 안된다.

 

◽Kruskal 알고리즘

크루스칼 알고리즘은 위에 말한 MST 를 구하는 알고리즘이며, greedy 하게 모든 정점을 최소 비용으로 연결하는, 결정의 순간마다 최선의 결정을 함으로써 최종적인 해답에 도달한다.

크루스칼 알고리즘의 핵심은 모든 간선의 가중치 기준으로 오름차순 정렬하고, 이를 기반으로 간선들을 순서대로 모든 정점이 연결될 때까지 연결한다. Union-find 알고리즘을 이용하여 구현할 수 있고, 이를 통해 사이클이 형성되지 않으면서 모든 정점을 연결할 수 있다.

 

크루스칼 알고리즘은 O (ElogV) 의 시간복잡도를 가진다. 간단히 말하면, 모든 가중치를 정렬하는데 걸리는 시간이 O(ElogE) 시간복잡도를 갖는데, 크루스칼 알고리즘에서 이 연산보다 영향력이 있는 연산은 없기 때문에 최종적으로 O(ElogE) 가 걸린다고 생각하는 것이다. 이때, 간선의 수는 최대 V^2 개가 될 수 있으므로 O(logE) = O(logV^2) = O(2logV) = O(logV) 로 볼수 있고, 최종적으로 O(ElogV)의 시간 복잡도를 갖는다.

 

🔻Union-find (유니온-파인드) 알고리즘

대표적인 그래프 알고리즘으로 '합집합 찾기' 라는 의미를 가지고 있다. 서로소 집합(Disjoint-Set) 알고리즘이라고도 불린다. 구체적으로 여러 개의 노드가 존재할 때 두 개의 노드를 선택해서, 현재 이 두 노드가 서로 같은 그래프에 속하는 지 판별하는 알고리즘이다.

2가지 연산으로 이루어진다. 

- 1. Find : x 가 어떤 집합에 포함되어 있는지 찾는 연산

- 2. Union : x 와 y가 포함되어 있는 집합을 합치는 연산

 

🔻동작방식

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

2. 정렬된 간선 리스트를 순서대로 선택하여, 간선의 정점들을 연결한다. 이때 정점을 연결하는 것은 Union-Find 의 Union 으로 구현한다.

3. 만약 간선의 두 정점 a,b 가 연결되어 있다면 스킵.

4. 위의 과정을 반복하여 최소 비용의 간선들만 이용하여 모든 정점을 연결한다.

 

✅ 전체 코드

import java.util.*;
import java.util.stream.*;

public class Solution {
    static private int[] parent;

    public static void main(String[] args) {
        int n = 4;
        int[][] cost = {{0,1,1},{0,2,2},{1,2,5},{1,3,1},{2,3,8}};

        int answer = solution(n, cost);
        System.out.println(answer);
    }

    static int solution(int n, int[][] costs) {
        int answer = 0;
        parent = new int[n];
        
        // init
        for(int i=0; i<n; i++)
            parent[i] = i;
        
        // 가중치 기준 오름차순
        Arrays.sort(costs, (a, b) -> a[2] - b[2]);

        // Kruskal Algorithm
        for(int i=0; i<costs.length; i++) {
            // 두 정점이 연결되어 있지 않은 경우
            if(find(costs[i][0]) != find(costs[i][1])) {
                // 두 정점 연결
                union(costs[i][0], costs[i][1]);
                // 최소 비용의 간선들만 이용하여 모든 정점 연결
                answer += costs[i][2];
            }
        }

        return answer;
    }

    // 부모 노드 찾기
    static int find(int a) {
        if(parent[a] == a) return a;
        return parent[a] = find(parent[a]);
    }

    static void union(int a, int b) {
        a = find(a);
        b = find(b);
        if(a != b)
            parent[b] = a;
    }
}

 

 

◽Prim 알고리즘

프림 알고리즘도 위에 말한 최소 신장트리를 구하는 알고리즘이다. 프림은 임의의 시작점에서 현재까지 연결된 정점들에서 연결되지 않은 정점들에 대해 가장 가중치가 작은 정점을 연결하는 정점 선택 기반으로 동작한다.

 

프림의 핵심은 트리 집합을 단계적으로 확장하는 것이고, 새로운 정점을 연결할 때마다 새로운 정점에서 갈 수 있는 아직 연결되지 않은 정점들에 대한 간선을 추가해야 한다. PriorityQueue 를 이용한 최소 힙으로 구현할 수 있고, 다익스트라 알고리즘과 유사한 방식을 가진다.

 

🔻동작방식

1. 임의의 정점을 시작점으로 선택.

2. 시작점에서 갈 수 있는 정점 중 가장 가중치가 작은 정점을 연결.

3. 2번 과정에서 어떠한 정점과 연결된 경우, 연결된 정점들의 집합을 x집합이라고 하면 x집합에서 갈 수 있는 x집합에 포함되어 있지 않은 정점들에 대해서 가장 작은 가중치의 정점을 연결한다.

4. x 집합의 크기는 점점 커지며, 위 과정을 모든 정점들이 연결될 때까지 반복한다.

 

✅ 전체 코드

import java.util.*;
import java.util.stream.*;

public class Solution {
    static class Point implements Comparable<Point> {
        int node, cost;

        Point(int node, int cost) {
            this.node = node;
            this.cost = cost;
        }

        @Override
        public int compareTo(Point o) {
            return this.cost - o.cost;
        }
    }

    public static void main(String[] args) {
        int n = 4;
        int[][] cost = {{0,1,1},{0,2,2},{1,2,5},{1,3,1},{2,3,8}};

        int answer = solution(n, cost);
        System.out.println(answer);
    }

    static int solution(int n, int[][] costs) {
        int answer = 0;
        List<List<Point>> map = new ArrayList<>();
        for(int i=0; i<n; i++)
            map.add(new ArrayList<>());

        for(int[] c : costs) {
            int from = c[0];
            int to = c[1];
            int cost = c[2];

            map.get(from).add(new Point(to, cost));
            map.get(to).add(new Point(from, cost));
        }

        // Prim Alogrithm
        boolean[] visited = new boolean[n];
        PriorityQueue<Point> que = new PriorityQueue<>();
        que.add(new Point(0, 0));

        while(!que.isEmpty()) {
            Point cur = que.poll();

            if(visited[cur.node]) continue;
            visited[cur.node] = true;

            answer += cur.cost;

            for(int i=0; i<map.get(cur.node).size(); i++) {
                int next = map.get(cur.node).get(i).node;
                int cost = map.get(cur.node).get(i).cost;
                if(visited[next]) continue;
                que.add(new Point(next, cost));
            }

        }

        return answer;
    }
}