[BOJ] 2211번 네트워크 복구 - JAVA

💡 문제

💬 입출력 예시

📌 풀이(소스코드)

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

public class Main {
    static class Node implements Comparable<Node> {
        int index;
        int cost;

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

        @Override
        public int compareTo(Node o) {
            return Integer.compare(cost, o.cost);
        }
    }

    static final int INF = (int) 1e9;
    static int N, M, k;
    static int[] d, path;
    static ArrayList<ArrayList<Node>> graph = new ArrayList<>();
    static StringBuilder sb = new StringBuilder();

    public static void main(String[] args) throws IOException {
        init();
        process();
        print(k, sb);
    }

    private static void init() throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        N = Integer.parseInt(st.nextToken());
        M = Integer.parseInt(st.nextToken());
        d = new int[N + 1];
        path = new int[N + 1];
        Arrays.fill(d, INF);
        for (int i = 0; i <= N; i++) {
            graph.add(new ArrayList<>());
        }
        for (int i = 0; i < M; i++) {
            st = new StringTokenizer(br.readLine());
            int from = Integer.parseInt(st.nextToken());
            int to = Integer.parseInt(st.nextToken());
            int cost = Integer.parseInt(st.nextToken());
            graph.get(from).add(new Node(to, cost));
            graph.get(to).add(new Node(from, cost));
        }
    }

    private static void process() {
        dijkstra(1);
        setResults();
    }

    private static void dijkstra(int start) {
        PriorityQueue<Node> pq = new PriorityQueue<>();
        pq.add(new Node(start, 0));
        d[start] = 0;
        while (!pq.isEmpty()) {
            Node current = pq.poll();
            int curIdx = current.index;
            int curCost = current.cost;
            if (d[curIdx] < curCost) continue;
            ArrayList<Node> nextNodes = graph.get(curIdx);
            for (Node next : nextNodes) {
                int nextIdx = next.index;
                int cost = d[curIdx] + next.cost;
                if (cost < d[nextIdx]) {
                    d[nextIdx] = cost;
                    path[nextIdx] = curIdx;
                    pq.add(new Node(nextIdx, cost));
                }
            }
        }
    }

    private static void setResults() {
        for (int i = 1; i <= N; i++) {
            if (path[i] == 0) continue;
            k++;
            sb.append(i).append(" ").append(path[i]).append("\n");
        }
    }

    private static void print(int k, StringBuilder sb) {
        System.out.println(k);
        System.out.println(sb);
    }
}

📄 해설

• 무향 그래프에 대한 다익스트라 알고리즘을 수행하고, 최단 경로가 갱신될때마다, 그 경로를 저장한다는 아이디어를 얻으면 해결이 가능한 문제
• 최단 거리의 경로를 저장하기 위해 1차원 배열인 path 를 사용하였으며, 각각의 인덱스에는 해당 인덱스의 직전 인덱스 값이 저장을 하였음
  • 4번으로 가는 최단 경로가 1 - 2 - 4 일 때, path[4] = 2 가 되도록하였음
• 다익스트라 알고리즘을 수행하면서 최당 경로가 갱신이 될 때, 이를 갱신하면서 path 배열의 다음 정점 인덱스에 현재 정점의 인덱스 값을 담음 (path[nextIdx] = curIdx) -> dijsktra 메소드
• 다익스트라 알고리즘 수행 후, path 배열 내에서 값이 0인 지점을 제외하여 개수를 세고, 그 경로를 출력 -> setResults 메소드