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

1. 문제

---

프로그래머스

2. 풀이 과정

---

이 문제는 최소신장트리를 구현하는 문제이다.

최소신장트리란 가중치가 부여된 연결 그래프에서 모든 정점을 포함하면서, 모든 간선의 가중치 합이 최소가 되는 트리를 말한다.

 

최소신장트리를 구현하는 방법은 두 가지가 있다.

 

1. 크루스칼 알고리즘

 1) 간선들을 비용을 기준으로 오름차순으로 정렬한다.

 2) 적은 비용의 간선부터 시작해 해당 간선이 잇는 두 노드를 연결시킨다. 이때 사이클이 발생하지 않도록 주의해야한다.

 3) 모든 노드를 방문할 때까지 반복해 가중치의 합을 구한다.

 

 

2. 프림 알고리즘

 1) 임의의 노드를 하나 정해 방문한다.

 2) 해당 노드와 인접한 노드 중 가장 간선의 비용이 적은 노드를 방문한다.

 3) 방문한 노드들과 인접한 노드 중 가장 간선의 비용이 적은 노드를 방문한다. 

 4) 모든 노드를 방문할 때까지 반복해 가중치의 합을 구한다.

 

크루스칼 알고리즘은 유니온파인드를 통해 구현하고

프림 알고리즘은 우선순위 큐를 통해 구현한다.

 

코드로 바로 보도록하자.

3. 내 코드

---

1. 크루스칼 알고리즘

import java.util.*;
class Solution {
    
    class UnionFind {
        int[] parent;
        int[] rank;
        
        UnionFind(int n) {
            parent = new int[n];
            rank = new int[n];
            for(int i = 0; i < n; i++) {
                parent[i] = i;
                rank[i] = 0;
            }
        }
        void union(int x, int y) {
            int root_x = find(x);
            int root_y = find(y);

            if(root_x != root_y) {
                if(rank[root_x] > rank[root_y]) {
                    parent[root_y] = root_x;
                } else if(rank[root_x] < rank[root_y]) {
                    parent[root_x] = root_y;    
                } else {
                    parent[root_y] = root_x;
                    rank[root_x]++;
                }
            }
            
        }
        
        int find(int x) {
            
            if(parent[x] == x) {
                return x;
            }
            
            return find(parent[x]);
        }
    }
    public int solution(int n, int[][] costs) {
        
    // 크루스칼을 이용한 최소 신장 트리
        UnionFind unionFind = new UnionFind(n);
        
        // 1. 경로의 비용을 기준으로 오름차순 정렬하기
        Arrays.sort(costs, (o1, o2) -> Integer.compare(o1[2], o2[2]));
        
        // 2. 비용이 작은 순으로 경로를 연결시키기
        int cost_sum = 0;
        for(int[] info: costs) {
            int from = info[0];
            int to = info[1];
            int cost = info[2];
            
            if(unionFind.find(from) != unionFind.find(to)) {
                unionFind.union(from, to);
                cost_sum += cost;
            }
        
        }
        
        return cost_sum;
    }
}

시간 복잡도

• O(ElogE)
  E: 엣지(간선)의 갯수

 

2. 프림 알고리즘

import java.util.*;

class Solution {
    
    class Edge {
        int to;
        int cost;
        
        Edge(int to, int cost) {
            this.to = to;
            this.cost = cost;
        }
    }
    
    public int solution(int n, int[][] costs) {
        // 그래프를 인접 리스트 형태로 변환
        List<List<Edge>> graph = new ArrayList<>();
        for (int i = 0; i < n; i++) {
            graph.add(new ArrayList<>());
        }
        
        for (int[] cost : costs) {
            int from = cost[0];
            int to = cost[1];
            int weight = cost[2];
            graph.get(from).add(new Edge(to, weight));
            graph.get(to).add(new Edge(from, weight)); // 무향 그래프이므로 양방향 간선을 추가
        }
        
        // 프림 알고리즘을 사용하여 MST를 구성
        boolean[] visited = new boolean[n];
        PriorityQueue<Edge> pq = new PriorityQueue<>((e1, e2) -> e1.cost - e2.cost);
        
        // 시작 정점(0번 정점)에서부터 시작
        visited[0] = true;
        for (Edge edge : graph.get(0)) {
            pq.add(edge);
        }
        
        int cost_sum = 0;
        
        while (!pq.isEmpty()) {
            Edge edge = pq.poll();
            
            if (visited[edge.to]) continue;
            
            visited[edge.to] = true;
            cost_sum += edge.cost;
            
            for (Edge nextEdge : graph.get(edge.to)) {
                if (!visited[nextEdge.to]) {
                    pq.add(nextEdge);
                }
            }
        }
        
        return cost_sum;
    }
}

시간 복잡도

• O(ElogE)
  E: 엣지(간선)의 갯수

4. 피드백

---

• 최소신장트리는 크루스칼과 프림