[BOJ2211] 네트워크 복구 (최단 경로, 다익스트라, 그래프)

 

 

---

문제 링크 

https://www.acmicpc.net/problem/2211

2211번: 네트워크 복구

---

문제 풀이 

- 다익스트라 + 백트래킹

- 양방향 그래프

- N(노드) 최대 1,000, C (비용) 최대 10 이므로 최대치는 10,000이므로 int로 처리가능

- 루트 노드가 1번일 때, 다른 노드를 모두 연결하기 위해서는 N - 1개의 간선이 필요하다 (트리 생각하기!)

- 최단 경로를 갱신하면서 parent 배열에 이전 노드에 대한 정보 기록 (parent[도착노드] = 이전노드)

- 그리고 1을 제외한 parent 배열을 순차 조회하면서 결과 출력

- 시간복잡도 : O(ElogV) 

 

트리가 생각나서 쉽게 풀 수 있었다

---

제출 코드

import java.util.*;
import java.io.*;

public class Main {
    
    static StringBuilder sb = new StringBuilder();
    static InputProcessor inputProcessor = new InputProcessor();

    static int N, M;
    static List<List<Node>> ADJ;

    public static void main(String[] args) throws IOException {
        input();
        pro();
        output();
    }

    private static class Node implements Comparable<Node> {
        int idx;
        int cost;

        public Node(int idx, int cost) {
            this.idx = idx;
            this.cost = cost;
        }

        @Override
        public int compareTo(Node other) {
            return this.cost - other.cost; // 오름차순 정렬
        }
    }

    private static void input() {
        N = inputProcessor.nextInt();
        M = inputProcessor.nextInt(); // 간선의 수

        ADJ = new ArrayList<>();
        for(int i = 0; i <= N; i++) {
            ADJ.add(new ArrayList<>());
        }

        for(int i = 1; i <= M; i++) {
            int from = inputProcessor.nextInt();
            int to = inputProcessor.nextInt();
            int cost = inputProcessor.nextInt();

            ADJ.get(from).add(new Node(to, cost));
            ADJ.get(to).add(new Node(from, cost));
        }
    }

    private static void pro() {
        dijkstra(1);
    }

    private static void dijkstra(int start) {
        Queue<Node> que = new PriorityQueue<>();
        que.add(new Node(start, 0));

        int[] dist = new int[N + 1];
        Arrays.fill(dist, Integer.MAX_VALUE);
        dist[start] = 0;

        int[] parent = new int[N + 1];
        Arrays.fill(parent, -1);
        parent[start] = 0;

        while(!que.isEmpty()) {
            Node cur = que.poll();

            if(dist[cur.idx] < cur.cost) continue;

            for(Node next : ADJ.get(cur.idx)) {
                if(dist[next.idx] <= dist[cur.idx] + next.cost) continue;

                parent[next.idx] = cur.idx; // 여기 추가
                dist[next.idx] = dist[cur.idx] + next.cost;
                que.add(new Node(next.idx, dist[next.idx]));
            }
        }

        // 결과 출력
        sb.append(N - 1).append("\n");
        for(int i = 2; i <= N; i++) {
            sb.append(i).append(" ").append(parent[i]).append("\n");
        }
    }

    private static void output() throws IOException {
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        bw.write(sb.toString());
        bw.flush();
        bw.close();
    }

    private static class InputProcessor {
        BufferedReader br;
        StringTokenizer st;

        public InputProcessor() {
            this.br = new BufferedReader(new InputStreamReader(System.in));
        }

        public String next() {
            while(st == null || !st.hasMoreElements()) {
                st = new StringTokenizer(nextLine());
            }

            return st.nextToken();
        }

        public String nextLine() {
            String input = "";

            try {
                input = br.readLine();
            } catch (IOException e) {
                throw new RuntimeException(e);
            }

            return input;
        }

        public int nextInt() {
            return Integer.parseInt(next());
        }

        public long nextLong() {
            return Long.parseLong(next());
        }
    }
    
}