[BJ]2211. 네트워크 복구

BJ G2 2211 네트워크 복구

 

 

문제링크

2211번: 네트워크 복구 (acmicpc.net)

* 일단 문제를 정독 하고 1시간 이상 반드시 고민이 필요합니다.

 

동영상 설명

1시간 이상 고민 했지만 아이디어가 떠오르지 않는다면 동영상에서 약간의 힌트를 얻어봅시다.

https://youtu.be/Z62JkP5LH2o

 

 

소스보기

동영상 설명을 보고도 전혀 구현이 안된다면 연습 부족입니다.
소스를 보고 작성해 본 후 스스로 백지 상태에서 3번 작성해 볼 의지가 있다면 소스를 살짝 보세요.

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.StringReader;
import java.util.Arrays;
import java.util.PriorityQueue;
import java.util.StringTokenizer;

/**
 * @author 은서파
 * @since 2022. 3. 2.
 * @see
 * @performance
 * @category #
 * @memo
 */

public class Main {

    static BufferedReader input = new BufferedReader(new InputStreamReader(System.in));
    static StringBuilder output = new StringBuilder();
    static StringTokenizer tokens;

    static int V, E;
    static LinkNode[] graph;

    public static void main(String[] args) throws IOException {
        tokens = new StringTokenizer(input.readLine());
        V = Integer.parseInt(tokens.nextToken()) + 1;
        E = Integer.parseInt(tokens.nextToken());

        graph = new LinkNode[V];
        for (int e = 0; e < E; e++) {
            tokens = new StringTokenizer(input.readLine());
            int a = Integer.parseInt(tokens.nextToken());
            int b = Integer.parseInt(tokens.nextToken());
            int c = Integer.parseInt(tokens.nextToken());

            // 그래프 - 양방향 그래프
            graph[a] = new LinkNode(b, c, graph[a]);
            graph[b] = new LinkNode(a, c, graph[b]);
        }

        dijkstra();
        
        System.out.println(output);
    }

    // 중앙 컴퓨터(시작점) 다른 컴퓨터들(다른 정점들)에 접근하는 최소 비용 -> dijkstra,MST 아니다.!!!
    private static void dijkstra() {
        // 필요한 재료들
        int[] accumCost = new int[V];
        // PQ는 시작점에서 각 정점까지의 누적 거리를 기준으로 크기 비교
        PriorityQueue<LinkNode> pq = new PriorityQueue<>();

        // 초기 설정
        Arrays.fill(accumCost, Integer.MAX_VALUE);
        accumCost[1] = 0;
        pq.offer(new LinkNode(1, 0, -1));
        int cnt = 0;
        while (!pq.isEmpty()) {
            LinkNode head = pq.poll();

            // 방문체크
            if (accumCost[head.i] < head.ac) {
                continue;
            }
            // 연결 확장!! - 어디서와서 head와 연결되었는가?
            if(head.pi!=-1) {
                output.append(head.i+" "+head.pi).append("\n");
                cnt++;
            }

            LinkNode child = graph[head.i];
            while (child != null) {
                if (accumCost[child.i] > accumCost[head.i] + child.c) {
                    accumCost[child.i] = accumCost[head.i] + child.c;
                    pq.offer(new LinkNode(child.i, accumCost[child.i], head.i));
                }
                child = child.pre;
            }
        }
        output.insert(0, cnt+"\n");

    }

    static class LinkNode implements Comparable<LinkNode> {
        int i, c;
        LinkNode pre;
        int ac; // 누적 거리
        int pi; // 조상의 인덱

        public LinkNode(int i, int ac, int pi) {
            this.i = i;
            this.ac = ac;
            this.pi = pi;
        }

        public LinkNode(int i, int c, LinkNode pre) {
            super();
            this.i = i;
            this.c = c;
            this.pre = pre;
        }

        @Override
        public int compareTo(LinkNode o) {
            return Integer.compare(this.ac, o.ac);
        }

    }

    // REMOVE_START
    private static String src = "4 5\r\n" +
                                "1 2 1\r\n" +
                                "1 4 4\r\n" +
                                "1 3 2\r\n" +
                                "4 2 2\r\n" +
                                "4 3 3";
    // REMOVE_END    
}