[알고리즘] 백준 > #2211. 네트워크 복구

문제링크

백준 #2211. 네트워크 복구

풀이방법

슈퍼컴퓨터부터 다른 컴퓨터까지의 최소 시간은 다익스트라를 이용해 구할 수 있다. 근데 이 문제에서는 최소 시간이 아니라 그 최소 시간을 보장하는 "경로"에 대해 묻고있다. 즉, 다익스트라 알고리즘을 통해 사용한 경로를 묻고있다. 이 경로를 어떻게 구할까 생각해봤다. 만약에 4번 컴퓨터까지 가는 경로가 [1번 컴퓨터 - 2번 컴퓨터 - 4번 컴퓨터]라면, (1, 2)를 다 저장해야할까? 그렇지않다. 사실 부분 경로에 해당하는 [1번 컴퓨터 - 2번 컴퓨터]는 2번 컴퓨터까지의 경로이다. 따라서, 당장 앞에 지나온 컴퓨터만 저장하면 앞 컴퓨터를 역으로 타고 들어가 그 경로를 알 수 있다. 그래서 나는 times 값이 갱신되는 시점에 prevPC라는 배열에 그 값을 저장해 문제를 해결했다. 이런 테크닉은 이 문제 뿐만 아니라 여러 문제에서 유용하게 쓰일거같다!

코드

import java.util.*;

public class BOJ2211 {

    static final int MAX_COST = 10001;

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);

        int n = sc.nextInt();
        int m = sc.nextInt();

        LinkedList<Line>[] lines = new LinkedList[n + 1];
        for (int i = 1;i <= n; i++) lines[i] = new LinkedList<>();

        while (--m >= 0) {
            int a = sc.nextInt();
            int b = sc.nextInt();
            int c = sc.nextInt();

            lines[a].add(new Line(b, c));
            lines[b].add(new Line(a, c));
        }

        boolean[] visited = new boolean[n + 1];
        int[] prevPCs = new int[n + 1];
        int[] times = new int[n + 1];
        for (int i = 1; i <= n; i++) times[i] = MAX_COST;
        PriorityQueue<PCCost> q = new PriorityQueue<>();

        times[1] = 0;
        q.offer(new PCCost(1, times[1]));
        prevPCs[1] = 1;

        while (!q.isEmpty()) {
            PCCost head = q.poll();

            if (visited[head.currPC]) continue;

            visited[head.currPC] = true;
            for (Line nextLine : lines[head.currPC]) {
                if (!visited[nextLine.destPC] && (times[nextLine.destPC] > times[head.currPC] + nextLine.time)) {
                    times[nextLine.destPC] = times[head.currPC] + nextLine.time;
                    q.offer(new PCCost(nextLine.destPC, times[nextLine.destPC]));
                    prevPCs[nextLine.destPC] = head.currPC;
                }
            }
        }

        StringBuilder result = new StringBuilder();
        result.append((n - 1) + "\n");
        for (int i = 2; i <= n; i++) result.append(i + " " + prevPCs[i] + "\n");

        System.out.print(result.toString());
    }
}

class Line {
    public int destPC;
    public int time;

    public Line(int destPC, int time) {
        this.destPC = destPC;
        this.time = time;
    }
}

class PCCost implements Comparable<PCCost> {
    public int currPC;
    public int timeSum;

    public PCCost(int currPC, int timeSum) {
        this.currPC = currPC;
        this.timeSum = timeSum;
    }

    @Override
    public int compareTo(PCCost o) {
        return this.timeSum - o.timeSum;
    }
}