[백준 1753번] 최단경로 - JAVA

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

1753번: 최단경로

풀이

사용한 알고리즘 : 다익스트라

 

풀이전략

하나의 시작점에서 모든 노드를 가는데 필요한 최소값을 구하는 문제이다.

전형적인 다익스트라 사용 문제로, 자바를 사용한 경우 목표 지점과 목표 지점까지의 비용이 들어가는

클래스를 추가로 사용하면 된다.

 

동작 과정은 다음과 같다.

 

1. 출발 노드 설정

2. 최단 거리 테이블 초기화(모두 무한(1e9)으로 설정)

3. 출발 노드를 우선순위 큐에 삽입하고 다익스트라 알고리즘 시작

4. 큐에 삽인된 노드들 중 최단 거리가 가장 짧은 노드 선택(dequeue)

5. 해당 노드를 거쳐 다른 노드로 가는 비용을 계산하여 더 비용이 적게 든다면,

    최단 거리 테이블을 갱신하고 우선순위큐에 해당 노드 삽입(inqueue)

5. 4~5번 과정을 큐가 빌 때까지 반복

6. 최단 거리 테이블을 출력

 

이 알고리즘의 시간 복잡도는 O(ElogV)이다.

(E= 간선의 개수, V= 노드의 개수)

노드를 삭제하고 추가하는 연산은 우선순위 큐를 통해 힙 자료구조를 사용했으므로 O(logV)가 걸리고,

간선의 개수만큼 이를 반복하므로 최종적인 시간 복잡도는 O(ElogV) 이다.

 

제출코드

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

public class Main {
    static class Node implements Comparable<Node>{
        int objective;
        int cost;

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

        public int getObjective() {
            return objective;
        }

        public int getCost() {
            return cost;
        }

        // cost기준 오름차순 정렬
        @Override
        public int compareTo(Node o) {
            if(this.cost<o.cost) return -1;
            else return 1;
        }
    }
    static ArrayList<ArrayList<Node>> graph = new ArrayList<>();
    static int distance[];
    static int INF = (int)1e9;

    static void dijkstra(int start){
        PriorityQueue<Node> q = new PriorityQueue<>();
        q.offer(new Node(start,0));
        distance[start]=0;

        while(!q.isEmpty()){
            Node temp = q.poll();
            int now = temp.getObjective();

            if(distance[now]<temp.getCost()) continue;

            for(Node node:graph.get(now)){
                if(distance[node.getObjective()]>
                    distance[now]+node.getCost()){
                    distance[node.getObjective()]=distance[now]+node.getCost();
                    q.offer(new Node(node.getObjective(),distance[node.getObjective()]));
                }
            }
        }
    }

    public static void main(String args[]) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        StringTokenizer st = new StringTokenizer(br.readLine());

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

        int start = Integer.parseInt(br.readLine());

        distance = new int[V+1];
        for(int i=0;i<V+1;++i){
            graph.add(new ArrayList<Node>());
            distance[i]=INF;
        }

        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 cost = Integer.parseInt(st.nextToken());
            graph.get(a).add(new Node(b,cost));
        }

        dijkstra(start);
        for(int i=1;i<V+1;++i){
            if(distance[i]==(int)1e9) bw.write("INF\n");
            else bw.write(distance[i]+"\n");
        }
        bw.flush();
        bw.close();
    }
}