[java] 2211번- 네트워크 복구

다익스트라 문제이다.
주어진 조건에서

1. 해커가 다시 공격을 할 우려가 있기 때문에, 최소 개수의 회선만을 복구해야 한다. 물론, 그렇다면 아무 회선도 복구하지 않으면 되겠지만, 이럴 경우 네트워크의 사용에 지장이 생기게 된다. 따라서 네트워크를 복구한 후에 서로 다른 두 컴퓨터 간에 통신이 가능하도록 복구해야 한다.
2. 네트워크를 복구해서 통신이 가능하도록 만드는 것도 중요하지만, 해커에게 공격을 받았을 때 보안 패킷을 전송하는 데 걸리는 시간도 중요한 문제가 된다. 따라서 슈퍼컴퓨터가 다른 컴퓨터들과 통신하는데 걸리는 최소 시간이, 원래의 네트워크에서 통신하는데 걸리는 최소 시간보다 커져서는 안 된다.

최소 개수의 회선 이라는 단어때문에 MST인가? 라는 고민때문에 쉽사리 구현하지 못했는데, dijkstra는 현재 자신의 노드를 큐에서 꺼내 자신과 연결된 노드들의 cost를 갱신하고 난 시점에서 자신의 현재 최선의 cost == 최소거리가 된다.

1. 모든 갱신되는 노드는 prev node에 자신까지의 cost를 더해 갱신된다.
2. 또한, x -> u -> y를 통해 x->y의 최소 코스트 회선이 완성되면, x->u까지는 이미 최소 거리 코스트를 가지고 있다.
3. k-1개의 간선을 쓰는 것 보다, k개의 간선을 쓰는 것이 더 손해이다.

결론 :

모든 노드들을 '1과'연결하되, 최소한의 cost를 가지는 경로로 구성하면, 최소한의 간선개수(n-1)만을 사용하게 된다. (어째뜬 다른 노드들은 1을 거쳐 모두 연결될 수 있음

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
import java.util.PriorityQueue;
import java.util.Scanner;

class node implements Comparable<node>{
    int nx;
    int cost;
    node prev;
    public node(int nx, int cost, node prev){
        this.nx = nx;
        this.cost = cost;
        this.prev = prev;
    }

    @Override
    public int compareTo(final node o) {
        return this.cost - o.cost;
    }
}
public class Main {
    public static void main(String[] args) {
        //컴퓨터 v, 회선 e, 회선간 가중치cost
        //네트워크 -> 최소길이로 슈퍼컴에 가야함.
        //한대슈퍼컴 -> 최소한의 네트워크를 만들어야한다.
        //슈퍼컴은 모든 컴퓨터와 최소 시간으로 연결되어야함.
        Scanner scanner = new Scanner(System.in);
        int n = scanner.nextInt();
        int m = scanner.nextInt();
        List<node> graph[] = new ArrayList[n+1];
        for(int i=1; i<=n; i++){
            graph[i] = new ArrayList();
        }
        for(int i=0; i<m; i++){
            int v1 = scanner.nextInt();
            int v2 = scanner.nextInt();
            int cost = scanner.nextInt();
            graph[v1].add(new node(v2, cost, null));
            graph[v2].add(new node(v1, cost, null));
        }
        dijkstra(graph, n, m);
    }

    private static void dijkstra(final List<node>[] graph, final int n, final int m) {
        int dist[] = new int[n+1];
        int visit[] = new int[n+1];
        visit[1] = 1;
        int count=0;
        Arrays.fill(dist, Integer.MAX_VALUE);

        dist[1] = 0;
        PriorityQueue<node> pq = new PriorityQueue<>();
        pq.add(new node(1,0, null));
        while(!pq.isEmpty()){
            node now = pq.poll();
            for(node next : graph[now.nx]){
                if(dist[next.nx] > dist[now.nx]+next.cost){
                    dist[next.nx] = dist[now.nx]+next.cost;
                    next.prev = now;
                    pq.add(new node(next.nx, dist[next.nx], now));
                    setPrev(visit, next); //next는 now를 통해 현재 최선의 값에 도달한다.
                }
            }
        }

        StringBuilder sb = new StringBuilder();
        for(int i=1; i<=n; i++){
            if(prev[i]==i) continue;
            sb.append(prev[i]).append(" ").append(i).append("\n");
        }
        System.out.println(n-1);
        System.out.println(sb);
    }

    private static void setPrev(final int[] prev, final node now) {
        if(now.prev!=null){
            prev[now.nx] = now.prev.nx; // 이전노드에서->나로 넘어왔다는 뜻
        }
        return;
    }

}