문제 바로가기

나의 풀이

평범한 다익스트라로 풀었다. 파이썬으로 할때보다 확실히 구현이 많이 복잡해져서 풀이가 맞기는 했지만 시간도 1000ms에 가깝고, 메모리도 거의 100MB 가까이 사용해서 좀 더 효율적인 풀이를 생각도 해보고 찾아보았다.

500~600ms의 시간 내에 java로 이 문제를 해결한 다른 사람들의 풀이를 보니... 기본적인 println() 부터 시작해서 다양한 메서드들을 오버라이딩해서 최대한 단축시키는 것으로 보였다. 실제 기업용 코테에서는 알고리즘 측면에서 효율성을 이끌어내지 이렇게 자바의 라이브러리 자체를 뜯어고쳐서 효율성을 끌어내는 문제는 출제되지 않을 것 같아 더 이상 찾아보지는 않았다.

결론 : 다익스트라는 역시 오래걸린다.

우선순위 큐를 사용하는 다익스트라의 시간복잡도는 O(ElogV)

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

class Node implements Comparable<Node> {

    public int index;
    public int distance;

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

    @Override
    public int compareTo(Node o) {
        if (this.distance < o.distance) {
            return -1;
        }
        return 1;
    }
}

class Main {

    static final int INF = Integer.MAX_VALUE;
    static int v, e, k;
    static List<List<Node>> graph = new ArrayList<>();
    static int[] d = new int[20001];

    public static void main(String[] args) throws IOException {

        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        v = Integer.parseInt(st.nextToken());
        e = Integer.parseInt(st.nextToken());

        st = new StringTokenizer(br.readLine());
        k = Integer.parseInt(st.nextToken());

        for (int i = 0; i < v + 1; i++) {
            graph.add(new ArrayList<>());
        }

        for (int i = 0; i < e; i++) {
            st = new StringTokenizer(br.readLine());
            int i1 = Integer.parseInt(st.nextToken());
            int i2 = Integer.parseInt(st.nextToken());
            int i3 = Integer.parseInt(st.nextToken());
            graph.get(i1).add(new Node(i2, i3));
        }

        Arrays.fill(d, INF);

        dijkstra(k);
        for (int i = 1; i <= v; i++) {
            if (d[i] == Integer.MAX_VALUE) {
                System.out.println("INF");
            } else {
                System.out.println(d[i]);
            }
        }
    }

    public static void dijkstra(int start) {
        Queue<Node> q = new PriorityQueue<>();
        q.offer(new Node(start, 0));
        d[start] = 0;
        while (!q.isEmpty()) {
            Node node = q.poll();
            int dist = node.distance;
            int now = node.index;
            if (d[now] < dist) continue;
            for (int i = 0; i < graph.get(now).size(); i++) {
                int cost = d[now] + graph.get(now).get(i).distance;
                if (cost < d[graph.get(now).get(i).index]) {
                    d[graph.get(now).get(i).index] = cost;
                    q.offer(new Node(graph.get(now).get(i).index, cost));
                }
            }
        }
    }
}