[다익스트라] 최단경로

백준 1753 최단경로

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

52번의 제출. 계속 시간초과.  15시간만에 맞췄다. 

다익스트라 개념을 잘못알고 있었음.

잘못된 코드

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 ArrayList<Edge>[] adj;
    static int[] cost; //출발점에서 해당 지점까지 가는 비용
    static final int INF = Integer.MAX_VALUE;
    static int[] visited;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        int V = Integer.parseInt(st.nextToken()); //노드수
        int E = Integer.parseInt(st.nextToken()); //간선수
        int K = Integer.parseInt(br.readLine()); //시작정점

        adj = new ArrayList[V+1];
        cost = new int[V+1];
        visited = new int[V+1];
        Arrays.fill(cost, INF);

        for(int i=0; i<E; i++){
            st = new StringTokenizer(br.readLine());
            int u = Integer.parseInt(st.nextToken());
            int v = Integer.parseInt(st.nextToken());
            int w = Integer.parseInt(st.nextToken());

            if(adj[u]==null) adj[u] = new ArrayList<>();
//            if(adj[v]==null) adj[v] = new ArrayList<>();
            adj[u].add( new Edge(v, w) );
        }

        dijkstra(K);

        StringBuilder sb = new StringBuilder("");
        for(int i=1; i<=V; i++){
            if(cost[i]!=INF) sb.append( cost[i]+"\n" );
            else sb.append( "INF\n" );
        }
        System.out.println(sb);
    }

    static void dijkstra(int K){

        PriorityQueue<Edge> q = new PriorityQueue<>();
        q.offer( new Edge(K,0) );
        cost[K]=0;

        while(!q.isEmpty()){

            Edge edge = q.poll();
            int now = edge.v2; //지금노드

            if(visited[now]==0) visited[now] = 1;
            if( adj[now]==null ) continue;


            //지금거에 연결된 다음 노드들 확인
            Edge nextEdge;
            for(int i=0; i<adj[now].size(); i++){
                nextEdge = adj[now].get(i);

                if(nextEdge.v2 == now) continue;

                if( cost[now]+ nextEdge.weight < cost[nextEdge.v2]){
                    cost[nextEdge.v2] = cost[now]+nextEdge.weight;
                    q.offer( nextEdge );
                }
            }
        }
    }

    static class Edge implements Comparable<Edge>{
        int v2;
        int weight;

        Edge(int v2, int weight){
            this.v2 = v2;
            this.weight = weight;
        }

        @Override
        public int compareTo(Edge o) {
            if(this.weight < o.weight) return -1;
            else if(this.weight == o.weight) return 0;
            else return 1;
        }
    }
}

사실 이렇게 해도 답은 나오는데 시간초과 걸림.

PriorityQueue에 간선을 넣고, 간선 하나의 비용의 최솟값을 찾아서 비용을 비교한다.

이렇게 되면 똑같은 연산을 여러번 하게 된다.

어떤 간선까지 오기까지 비용이 엄청 많이 들어도 그 간선자체의 비용이 낮다면 높은 우선순위를 가진다.

다익스트라는 축적된 비용의 최솟값을 구하고, 하나의 노드는 한번만 사용한다.

이 알고리즘에서는 B에서 출발한 1짜리들이 Priority Queue에서 앞쪽에 위치하여 먼저 계산되어 버린다.

다익스트라에서 1짜리들은 B까지 비용이 많이 들기때문에 나중에 계산되며, A에서 출발한 간선부터 계산될 것이다.

어자피 모든 간선이 계산되긴 하지만 1짜리들은 비용이 높으므로 A에서 간 애들에 의해 다시 계산되어질 것이다.

A->B순서보다 B->A순서가 총 연산량이 더 많게 된다.  (이것때문일 것 같음) 

for(int i=1; i<=V; i++) {
        if(vCost[i]==INF) System.out.println("INF"); //갈 수 없는 곳
        else System.out.println(vCost[i]); //
}

StringBuilder sb = new StringBuilder("");
for(int i=1; i<=V; i++){
    if(cost[i]!=INF) sb.append( cost[i]+"\n" );
    else sb.append( "INF\n" );
}
System.out.println(sb);

처음에는 5%에서 시간초과로 짤렸는데 출력부분 수정 후 75%가지는 갔다. 출력을 300000개나 해야되기때문에 출력에 주어지는 부담이 꽤 크다.

수정된 코드

public class Main {

    static ArrayList<Edge>[] adj;
    static int[] cost; //출발점에서 해당 지점까지 가는 비용
    static final int INF = Integer.MAX_VALUE;
    static int[] visited;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        int V = Integer.parseInt(st.nextToken()); //노드수
        int E = Integer.parseInt(st.nextToken()); //간선수
        int K = Integer.parseInt(br.readLine()); //시작정점

        adj = new ArrayList[V+1];
        cost = new int[V+1];
        visited = new int[V+1];
        Arrays.fill(cost, INF);

        for(int i=0; i<E; i++){
            st = new StringTokenizer(br.readLine());
            int u = Integer.parseInt(st.nextToken());
            int v = Integer.parseInt(st.nextToken());
            int w = Integer.parseInt(st.nextToken());

            if(adj[u]==null) adj[u] = new ArrayList<>();
            if(adj[v]==null) adj[v] = new ArrayList<>();
            adj[u].add( new Edge(v, w) );
        }

        dijkstra(K);

        StringBuilder sb = new StringBuilder("");
        for(int i=1; i<=V; i++){
            if(cost[i]!=INF) sb.append( cost[i]+"\n" );
            else sb.append( "INF\n" );
        }
        System.out.println(sb);
    }

    static void dijkstra(int K){

        PriorityQueue<Node> q = new PriorityQueue<>();
        q.offer( new Node(0,K) );
        cost[K]=INF;

        while(!q.isEmpty()){

            Node node = q.poll();
            int now = node.idx; //지금노드

            if(visited[now]==0) visited[now] = 1; else continue;
            if(node.cost < cost[now]) cost[now] = node.cost; else continue;

            Edge nextEdge;
            //지금거에 연결된 다음 노드들 확인
            for(int i=0; i<adj[now].size(); i++){
                nextEdge = adj[now].get(i);
                q.offer( new Node(cost[now]+nextEdge.weight, nextEdge.v2) );
            }
        }
    }

    static class Node implements Comparable<Node>{
        int cost; //출발점으로부터 비용
        int idx;

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

        @Override
        public int compareTo(Node o) {
            if(this.cost < o.cost) return -1;
            else if(this.cost == o.cost) return 0;
            else return 1;
        }
    }

    static class Edge{
        int v2;
        int weight;

        Edge(int v2, int weight){
            this.v2 = v2;
            this.weight = weight;
        }
    }
}

Node객체에 (출발점에서부터의 비용, 노드번호)를 넣어서 비교

개념참고: https://jason9319.tistory.com/307