[Baekjoon] 네트워크 연결

문제 : https://www.acmicpc.net/problem/1922

정점들이 주어지고, 정점간을 잇는 가중치가 주어졌을 때 모든 정점을 잇는 최소비용을 구하는 문제이다.

* 풀이

무방향 그래프에서 모든 정점을 잇는 간선의 비용이 최소로 되게끔 구현하는 MST구현 문제이다.

일반적으로 MST문제는 Kruskal, Prim 알고리즘으로 구현한다고 배웠다.

처음에는 주어진 정점, 가중치들을 인접행렬로 나타낸 후, 가중치 순으로 오름차순 정렬하고 하나씩 이어나가는 Kruskal알고리즘으로 구현해 보았다. 

그러나 cycle검사 처리를 dfs로 구현하다보니 2초라는 시간을 초과하였다. 해결책을 찾지 못하고 우선 Prim로 구현하여 해결하였다.

*코드 

 
package feb08.shortestpath;
 
import java.util.ArrayList;
import java.util.List;
import java.util.PriorityQueue;
import java.util.Scanner;
 
public class Main {
    
    class Node implements Comparable<Node> {
        
        int u, w;
        public Node(int u, int w) {
            super();
            this.u = u;
            this.w = w;
        }
        @Override
        public int compareTo(Node o) {
            // TODO Auto-generated method stub
            return w <= o.w  ? -1 : 1;
        }
        
    }
 
    public static void main(String[] args) {
        // TODO Auto-generated method stub
 
        int N, M;
        boolean[] visited;
        int last = 0;
        int sum = 0;
        Scanner sc = new Scanner(System.in);
        Main p = new Main();
        
        N = sc.nextInt();
        M = sc.nextInt();
        List<List<Node>> list = new ArrayList<List<Node>>();
        for(int i = 0; i < N; i++){
            list.add(new ArrayList<Main.Node>());
        }
        
        
        
        
        visited = new boolean[N];
        PriorityQueue<Node> pq = new PriorityQueue<Main.Node>();
        
        visited[last] = true;
        for(int i = 0; i < M; i++){
            
            int n1 = sc.nextInt() - 1;
            int n2 = sc.nextInt() - 1;
            int w = sc.nextInt();
 
            Node node1 = p.new Node(n1, w);
            Node node2 = p.new Node(n2, w);
            
            list.get(n2).add(node1);
            list.get(n1).add(node2);
        }
        
        for(int i = 0; i < N - 1 ; i++){
            
            int min = Integer.MAX_VALUE;
            int v = 0;
            
            for(int j = 0; j < list.get(last).size(); j++){
                int n = list.get(last).get(j).u;
                int w = list.get(last).get(j).w;
                
                pq.offer(p.new Node(n, w));
            }
            
            while(!pq.isEmpty()){
                
                Node node = pq.poll();
                int n = node.u;
                int w = node.w;
                
                if(!visited[n] && w < min){
                    min = w;
                    v = n;
                    break;
                }
            }
            visited[v] = true;
            sum += min;
            last = v;
            
        }
        System.out.println(sum);
    }
 
}
 

검색을 통하여 union-find 라는 cycle검사에 사용되는 효율적인 알고리즘을 알게 되었다. 이 부분을 좀 더 공부해 봐야 겠다.