[백준] BOJ2211네트워크 복구

https://www.acmicpc.net/problem/2211 네트워크 복구라는 문제인데 해당 문제를 풀기 위해 아래 2가지 알고리즘을 사용했다. 1) 다익스트라 2) 프림

import java.io.BufferedReader;
import java.io.FileInputStream;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Comparator;
import java.util.LinkedList;
import java.util.PriorityQueue;
import java.util.Queue;
import java.util.StringTokenizer;

public class BOJ2211 {
	
	static int N, E;
	static ArrayList[] list;
	
	static int START = 1;
	static int d[];
	
	static class Node{
		int v;
		int w;
		Node(int v, int w){
			this.v = v;
			this.w = w;
		}
	}
	
	static class Edge{
		int v1;
		int v2;
		int w;
		public Edge(int v1, int v2, int w) {
			this.v1 = v1;
			this.v2 = v2;
			this.w = w;
		}
	}
	
	static Comparator minHeap = new Comparator() {
		@Override
		public int compare(Node a, Node b) {
			return a.w - b.w;
		}
	};
	
	static Comparator minHeap2 = new Comparator() {
		@Override
		public int compare(Edge a, Edge b) {
			return a.w - b.w;
		}
	};
	
	public static void main(String[] args) throws Exception {
		System.setIn(new FileInputStream("src/input.txt"));
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());
		
		/* INPUT */
		N = Integer.parseInt(st.nextToken());
		E = Integer.parseInt(st.nextToken());
		
		list = new ArrayList[N+1];
		for(int i=1; i<=N; i++) {
			list[i] = new ArrayList();
		}
		
		int v1, v2, w;
		for(int i=1; i<=E; i++) {
			st = new StringTokenizer(br.readLine());
			v1 = Integer.parseInt(st.nextToken());
			v2 = Integer.parseInt(st.nextToken());
			w = Integer.parseInt(st.nextToken());
			
			list[v1].add(new Node(v2, w));
			list[v2].add(new Node(v1, w));
		}
		
		/* dijkstra */
		dijkstra();  
		
		/* Prim */
		Queue q = new LinkedList();
		PriorityQueue eList = new PriorityQueue(minHeap2);
		boolean[] visited = new boolean[N+1];
		
		q.add(START);
		visited[START] = true;
		
		
		int now;
		
		System.out.println(N-1);
		while( !q.isEmpty() ) {
			now = q.poll();
			
			// 갈 수 있는 간선 대상을 만드는 작
			// now 에서 갈 수 있는 모든 간선을 추가하는 데, "현재 노드까지의 w를 더해준다" 
			for(Node edge : list[now]) {
				eList.add(new Edge(now, edge.v , edge.w + d[now]));
			}
			
			// 간선 고르기 작업 
			while( !eList.isEmpty() ) {
				Edge e = eList.poll();
				
				if( !visited[e.v2] && e.w <= d[e.v2] ) {
					// 간선을 고른다.
					System.out.println(e.v1+" "+e.v2);
					
					q.add(e.v2);
					visited[e.v2] = true;
					break;
				}
			}
		}
		
		
		
	}
	
	
	public static void dijkstra() {
		d = new int[N+1];
		Arrays.fill(d, Integer.MAX_VALUE);
		d[START] = 0;
		
		PriorityQueue pq = new PriorityQueue(minHeap);
		
		pq.add(new Node(START, d[START]));
		
		Node n;
		while( !pq.isEmpty() ) {
			n = pq.poll();
			
			if( n.w != d[n.v] ) {
				continue;
			}
			
			for( Node nxt : list[n.v] ) {
				if( nxt.w + d[n.v] < d[nxt.v] ) {
					d[nxt.v] = nxt.w + d[n.v];
					pq.add(new Node(nxt.v, d[nxt.v]));
				}
			}
			
		}
	}
}