문제설명

N개의 마을에 각각 사람이 한 명씩 살고 있다. 이 마을 중 한개의 마을X에서 사람들이 모이기로했다. 마을들을 잇는 도로는 총 M개이며 단방향이다.
X 마을에 사는 사람을 제외하고는 모두 X마을로 갔다가 다시 자기 마을로 돌아가야한다.
이때, 왕복거리가 가장 긴 시간을 구하시오.
N은 최대 1000, M은 최대 10000

접근

그냥 가장 쉬운 방법인 플로이드 워셜 알고리즘의 시간복잡도를 생각해보았으나 너무 커서 불가능하다고 판단하고, 다익스트라를 그냥 두 번 왕복한 것을 더하면 한명에 대한 왕복시간이라고 생각해서 시간복잡도를 구해보았다. 다익스트라를 최소힙(우선순위큐)을 사용해서 구현한 경우 시간 복잡도는 O(ElogV)다. 대략 10만이고, 2번씩(왕복해야함) 해야하므로, 20만번이다. 근데, 최대 1000의 정점이 있으므로, 대략 2억번 정도의 연산이 필요하다.
하지만, 시간 제한은 1초였다. 그런데 잘생각해보면 정말로 2억번을 다 연산할 필요가 없다. 다익스트라를 진행하다가 내가 도착하고 싶은 지점에 도달하면 그냥 다익스트라를 끝내면 되기 때문이다. 이것에 대한 구체적인 시간 복잡도를 계산한 것은 아니였어서 사실 의심반 걱정반으로 일단 구현해보기로 했다.

풀이

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

public class Main {
    static int N;
    static int M;
    static int X;

    static ArrayList<Node>[] graph;
    static boolean[] isVisited;
    static int[] dijkstraTable;

    static class Node {
        final int number;
        final int distance;

        Node(int number, int d) {
            this.number = number;
            this.distance = d;
        }
    }

    public static void main(String[] args) 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());
        X = Integer.parseInt(st.nextToken());

        graph = new ArrayList[N + 1];
        for (int i = 0; i < N + 1; i++) graph[i] = new ArrayList<>();

        for (int i = 0; i < M; i++) {
            st = new StringTokenizer(br.readLine());
            int s = Integer.parseInt(st.nextToken());
            int e = Integer.parseInt(st.nextToken());
            int d = Integer.parseInt(st.nextToken());
            graph[s].add(new Node(e, d));
        }

        int max = 0;
        for (int i = 1; i <= N; i++) {
            if (i == X) continue;
            int sum = dijkstra(i, X) + dijkstra(X, i);
            max = Math.max(sum, max);
        }

        System.out.println(max);
    }

    static int dijkstra(int start, int end) {
        isVisited = new boolean[N + 1];
        dijkstraTable = new int[N + 1];
        PriorityQueue<Node> pq = new PriorityQueue<>((o1, o2) -> {
            if (o1.distance > o2.distance) {
                return 1;
            } else {
                return -1;
            }
        });
        pq.add(new Node(start, 0));

        for (int i = 1; i <= N; i++) {
            dijkstraTable[i] = Integer.MAX_VALUE;
        }
        dijkstraTable[start] = 0;


        while (!pq.isEmpty()) {
            Node curNode = pq.poll();
            if (isVisited[curNode.number]) continue;
            isVisited[curNode.number] = true;
            if (curNode.number == end) {
                return curNode.distance;
            }

            for (Node node : graph[curNode.number]) {
                if (isVisited[node.number]) continue;
                int origin = dijkstraTable[node.number];
                int newDistance = curNode.distance + node.distance;
                if (origin > newDistance) {
                    pq.add(new Node(node.number, newDistance));
                    dijkstraTable[node.number] = newDistance;
                }
            }
        }
        return 0;
    }
}

느낀점

다익스트라를 한점에서 다른 특정 한점까지만의 거리가 궁금해서 쓰는거라면 모든 연산을 하지 않기 때문에 생각보다 시간복잡도가 작다라는 것을 느꼈다(게다가 모든 노드에 대해 이런 작업을 반복한다면 분명 확률적으로 엄청 빨리 끝나는 경우가 꽤나 많을 것이다).

다시 풀어보았다.

다익스트라를 다시 공부하는 계기가 되었다. 최근에 안쓰다보니 조금 까먹었다....
이번에 실수한 부분은 다음과 같다.
1. 우선순위큐에 필수적으로 넣어야하는 정렬 조건을 내가 넣지 않음.
2. 다익스트라 알고리즘에서 쓰이는 테이블은 단순히 현재까지의 최단 경로를 말하는거지. 거기 있는 데이터가 항상 최단이 아님.
2. 현재 노드를 기준으로 이웃한 노드를 살펴보는 와중에 방문한 것은 아직 다익스트라의 선택을 받은 것이 아님. 다익스트라의 선택을 받기 위해서는 우선순위큐 while문에서 poll()로 뽑혀 나와야함.

3번에서 가장 헤맸는데, 내가 dijkstra함수의 종료문을 현재방문노드의 주변 이웃을 탐색하다가 최단경로 갱신이 되는 경우에서 수행해서 그랬다... 해당 로직을 while문의 poll() 아래에서 수행해주니 잘 됐다.

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

class Main {
    static int N;
    static int M;
    static int X;
    static ArrayList<Node>[] graph;
    static int[] go;
    static int[] back;
    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        N  = Integer.parseInt(st.nextToken());
        M = Integer.parseInt(st.nextToken());
        X = Integer.parseInt(st.nextToken());

        graph = new ArrayList[N+1];
        for(int i=1; i<=N; i++) graph[i] = new ArrayList<>();
        for(int i=0; i<M; i++) {
            st = new StringTokenizer(br.readLine());
            int n1  = Integer.parseInt(st.nextToken());
            int n2 = Integer.parseInt(st.nextToken());
            int cost = Integer.parseInt(st.nextToken());
            graph[n1].add(new Node(n2, cost));
        }
        go = new int[N+1];
        back = new int[N+1];

        for(int i=1; i<=N; i++) {
            if (i==X) continue;
            dijkstra(i);
        }
        dijkstra(X);
        go[X] = 0;
        back[X] = 0;

        int max = 0;
        for(int i=1; i<=N; i++) {
            if (i==X) continue;
            max = Math.max(max, go[i] + back[i]);
        }
        System.out.println(max);
    }

    static void dijkstra(int s) {
        int[] table = new int[N+1];
        Arrays.fill(table, Integer.MAX_VALUE);
        PriorityQueue<Node> pq = new PriorityQueue<>((n1, n2)-> {
            return n1.cost - n2.cost;
        });
        pq.add(new Node(s,0));
        table[s] = 0;

        while(!pq.isEmpty()) {
            Node curNode = pq.poll();
            if (s!=X && X==curNode.n) break;

            for(Node next: graph[curNode.n]) {
                int newCost = curNode.cost + next.cost;
                if (newCost < table[next.n]) {
                    table[next.n] = newCost; // 테이블에는 현재까지의 최단 거리를 저장.
                    pq.add(new Node(next.n, newCost));
                }
            }
        }

        if (s!=X) {
            go[s] = table[X];
        } else {
            back = table;
        }
    }
}

class Node {
    int n;
    int cost;
    Node(int n, int cost) {
        this.n = n;
        this.cost = cost;
    }
}