[프로그래머스 / Lv.3] - 섬 연결하기 (Java)

문제

---

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

프로그래머스

 

---

문제 풀이

---

이 문제는 최소 스패닝 트리를 찾는 문제로, 프림 알고리즘을 사용해 해결할 수 있다.

 

※ 최소 스패닝 트리

최소 스패닝 트리(Minimum Spanning Tree, MST)는 그래프에서 모든 노드를 최소 비용으로 연결하는 개념이다.

 

최소 스패닝 트리를 구하는 방법으로 대표적으로, 크루스칼 알고리즘과 프림 알고리즘이 존재한다.

 

크루스칼 알고리즘

- 모든 엣지를 가중치 순으로 정렬하고, 가중치가 낮은 엣지부터 선택해 사이클을 만들지 않도록 추가하는 방식

- 주로 유니온-파인드 자료 구조를 사용해 사이클 생성을 방지한다.

- (O(E \log E)), 여기서 (E)는 엣지의 수

 

프림 알고리즘

- 하나의 시작 노드에서 출발하여, 연결된 노드들 중 가장 가중치가 낮은 엣지를 선택하며 트리를 확장해 나가는 방식이다.

- 주로 우선순위 큐를 사용해 구현한다.

- 우선순위 큐를 사용하면 (O(E \log V)), 여기서 (E)는 엣지의 수, (V)는 노드의 수

 

현재 문제에서 노드보다 엣지의 개수가 많은 밀집 그래프이므로 효율적인 프림 알고리즘을 사용한다.

 

1. 그래프 초기화: 각 섬을 노드로 보고, 다리를 엣지로 보는 그래프를 초기화한다.

2. 프림 알고리즘 구현: 우선순위 큐를 사용해 비용이 가장 적은 엣지부터 선택해 MST를 구성한다.

 

코드 구현

import java.util.*;

class Solution {
    private List<Edge>[] graph;

    public int solution(int n, int[][] costs) {
        init(n, costs);
        return findMinimumCostToConnectAllIslands(n);
    }

    private void init(int n, int[][] costs) {
        graph = new List[n];
        for (int i = 0; i < n; i++) {
            graph[i] = new ArrayList<>();
        }

        for (int[] cost : costs) {
            int island1 = cost[0];
            int island2 = cost[1];
            int bridgeCost = cost[2];

            graph[island1].add(new Edge(island1, island2, bridgeCost));
            graph[island2].add(new Edge(island2, island1, bridgeCost));
        }
    }

    private int findMinimumCostToConnectAllIslands(int n) {
        PriorityQueue<Edge> pq = new PriorityQueue<>();
        boolean[] visited = new boolean[n];
        int totalCost = 0;
        int connectedIslands = 0;

        // Start from the first island
        visited[0] = true;
        for (Edge edge : graph[0]) {
            pq.add(edge);
        }

        while (!pq.isEmpty() && connectedIslands < n - 1) {
            Edge currentEdge = pq.poll();
            if (!visited[currentEdge.to]) {
                visited[currentEdge.to] = true;
                totalCost += currentEdge.cost;
                connectedIslands++;

                for (Edge edge : graph[currentEdge.to]) {
                    if (!visited[edge.to]) {
                        pq.add(edge);
                    }
                }
            }
        }

        return totalCost;
    }

    private static class Edge implements Comparable<Edge> {
        int from, to, cost;

        public Edge(int from, int to, int cost) {
            this.from = from;
            this.to = to;
            this.cost = cost;
        }

        @Override
        public int compareTo(Edge other) {
            return Integer.compare(this.cost, other.cost);
        }
    }
}