BOJ#1753 최단경로

BOJ#1753 최단경로

* 문제

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

* 풀이

다익스트라 최단 경로 문제입니다.주의할 점으로는 V와 E의 범위입니다. (1 <= V <= 20,000, 1 <= E <= 300,000)

1.

간선을 인접행렬로 구현한다면

sizeOf(int) * 20,000 * 20,000 = 1600 Mbytes 의 메모리가 필요합니다.

(그리고 4억개의 int 정보 중에 단 30만개만 사용)

2. 일반적으로 희소 그래프(sparse graph), 즉 정점^2보다 훨씬 작은 개수의 간선을 갖는 그래프에 대해서는 인접 리스트로 구현한 우선순위 큐를 이용해 다익스트라 알고리즘을 훨씬 더 효율적으로 구현할 수 있습니다.

따라서 이 문제에서 간선은 인접리스트로 구현해야 합니다.

가중치의 최대값이 10이므로 이를 이용하여 가중치도 입력 받았습니다.(50 라인)

* 다익스트라 알고리즘 - 시간 복잡도

1. 우선순위 큐를 사용하는 경우

1) 

우선순위 큐 최대 사이즈 = E

우선순위 큐에 원소를 추가,삭제 = logE

-> O(ElogE)

2)

각 정점을 한번씩 돌면서 연결된 간선 검사 = O(E)

O(E + ElogE) -> O(ElogE)

일반적으로 E는 V^2보다 작으므로

O(ElogV)

2. 우선순위 큐를 사용하지 않는 경우

다음에 방문할 정점을 우선순위 큐에 넣는 대신

매번 반복문을 이용하여 방문하지 않은(visited) 정점 중 dist가 가장 작은 정점을 찾는다.

O(V^2)

---

* 나의 코드

https://github.com/stack07142/BOJ/tree/master/BOJ%231753_ShortestPath/src

런타임 에러 소스(메모리 부족)

import java.io.*;
import java.util.Arrays;
import java.util.PriorityQueue;
import java.util.StringTokenizer;

/**
 * BOJ#1753 최단경로
 * https://www.acmicpc.net/problem/1753
 */

public class Main {

    static final int INF = 10000000;

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

        int V; // 정점의 개수 <= 20,000
        int E; // 간선의 개수 <= 300,000
        int[][] W; // 간선의 가중치
        int[] dist;
        int startNode;

        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

        StringTokenizer st = new StringTokenizer(br.readLine());

        V = Integer.parseInt(st.nextToken());
        E = Integer.parseInt(st.nextToken());

        W = new int[V + 1][V + 1];
        dist = new int[V + 1];

        for (int i = 0; i < V + 1; i++) {

            Arrays.fill(W[i], INF);
            Arrays.fill(dist, INF);
        }

        startNode = Integer.parseInt(br.readLine());

        for (int i = 0; i < E; i++) {

            st = new StringTokenizer(br.readLine());

            int a = Integer.parseInt(st.nextToken());
            int b = Integer.parseInt(st.nextToken());
            int w = Integer.parseInt(st.nextToken());

            W[a][b] = W[a][b] > w ? w : W[a][b];
        }

        dijkstra(startNode, V, W, dist);

        for (int i = 1; i < V + 1; i++) {

            bw.write(dist[i] < INF ? dist[i] + "\n" : "INF\n");
        }

        bw.flush();
        bw.close();
        br.close();
    }

    static void dijkstra(int src, int V, int[][] W, int[] dist) {

        PriorityQueue<Element> pq = new PriorityQueue<>();

        dist[src] = 0;

        pq.add(new Element(src, dist[src]));

        while (!pq.isEmpty()) {

            int cost = pq.peek().dist;
            int here = pq.peek().node;

            pq.poll();

            if (dist[here] < cost) {

                continue;
            }

            for (int i = 1; i < V + 1; i++) {

                if (W[here][i] < INF) {

                    if (dist[i] > dist[here] + W[here][i]) {

                        dist[i] = dist[here] + W[here][i];
                        pq.add(new Element(i, dist[i]));
                    }
                }
            }
        }
    }
}

class Element implements Comparable<Element> {

    int node;
    int dist;

    Element(int node, int dist) {

        this.node = node;
        this.dist = dist;
    }

    @Override
    public int compareTo(Element o) {

        return this.dist < o.dist ? -1 : 1;
    }

    @Override
    public String toString() {

        return "node=" + node + ", dist=" + dist;
    }
}

인접 리스트 이용한 코드

import java.io.*;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.PriorityQueue;
import java.util.StringTokenizer;

/**
 * BOJ#1753 최단경로
 * https://www.acmicpc.net/problem/1753
 */

public class Main {

    static final int INF = 5000000;

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

        int V; // 정점의 개수 <= 20,000
        int E; // 간선의 개수 <= 300,000
        ArrayList<ArrayList<Integer>> W = new ArrayList<>();
        int[] dist;
        int startNode;

        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

        StringTokenizer st = new StringTokenizer(br.readLine());

        V = Integer.parseInt(st.nextToken());
        E = Integer.parseInt(st.nextToken());

        dist = new int[V + 1];

        for (int i = 0; i < V + 1; i++) {

            Arrays.fill(dist, INF);
            W.add(new ArrayList<>());
        }

        startNode = Integer.parseInt(br.readLine());

        for (int i = 0; i < E; i++) {

            st = new StringTokenizer(br.readLine());

            int a = Integer.parseInt(st.nextToken());
            int b = Integer.parseInt(st.nextToken());
            int w = Integer.parseInt(st.nextToken());

            W.get(a).add(b * 11 + w);
        }

        dijkstra(startNode, V, W, dist);

        for (int i = 1; i < V + 1; i++) {

            bw.write(dist[i] < INF ? dist[i] + "\n" : "INF\n");
        }

        bw.flush();
        bw.close();
        br.close();
    }

    static void dijkstra(int src, int V, ArrayList<ArrayList<Integer>> W, int[] dist) {

        PriorityQueue<Element> pq = new PriorityQueue<>();

        dist[src] = 0;

        pq.add(new Element(src, dist[src]));

        while (!pq.isEmpty()) {

            int cost = pq.peek().dist;
            int here = pq.peek().node;

            pq.poll();

            if (dist[here] < cost) {

                continue;
            }

            for (int x : W.get(here)) {

                int adjNode = x / 11;
                int weight = x % 11;

                if (dist[adjNode] > dist[here] + weight) {

                    dist[adjNode] = dist[here] + weight;
                    pq.add(new Element(adjNode, dist[adjNode]));
                }
            }
        }
    }
}

class Element implements Comparable<Element> {

    int node;
    int dist;

    Element(int node, int dist) {

        this.node = node;
        this.dist = dist;
    }

    @Override
    public int compareTo(Element o) {

        return this.dist < o.dist ? -1 : 1;
    }
}