문제

---

[ 1753번: 최단경로 ]

방향그래프가 주어지면 주어진 시작점에서 다른 모든 정점으로의 최단 경로를 구하는 프로그램을 작성하시오. 단, 모든 간선의 가중치는 10 이하의 자연수이다.

문제 해결 방법

---

1. 첫 번째 아이디어: 다익스트라 알고리즘을 사용하여 최단 경로를 구한다.
   • 다익스트라 알고리즘은 하나의 시작 정점으로부터 모든 다른 정점까지의 최단 경로를 구하는 알고리즘이다.
   • 음의 간선이 없을 때 사용 가능하다.

코드

---

class Node implements Comparable<Node>{
    private int index, distance;

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

    public int getIndex(){
        return this.index;
    }

    public int getDistance(){
        return this.distance;
    }

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

public class Main {

    public static int[] d = new int[20001];
    public static ArrayList<ArrayList<Node>> graph = new ArrayList<ArrayList<Node>>();


    public static void dijkstra(int start){

        PriorityQueue<Node> pq = new PriorityQueue<>();
        pq.offer(new Node(start,0));
        d[start] = 0;
        while(!pq.isEmpty()){

            Node node = pq.poll();
            int dist = node.getDistance();
            int now = node.getIndex();

            if(d[now] < dist) continue;

            for(int i = 0; i<graph.get(now).size(); i++){
                int cost = d[now] + graph.get(now).get(i).getDistance();
                if(cost < d[graph.get(now).get(i).getIndex()]){
                    d[graph.get(now).get(i).getIndex()] = cost;
                    pq.offer(new Node(graph.get(now).get(i).getIndex(), cost));
                }
            }
        }

    }


    public static void main(String[] args) {

        Arrays.fill(d, Integer.MAX_VALUE);

        Scanner sc = new Scanner(System.in);
        int V = sc.nextInt();
        int E = sc.nextInt();
        int K = sc.nextInt(); 

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

        for(int i = 0; i<E; i++){
            int u = sc.nextInt();
            int v = sc.nextInt();
            int w = sc.nextInt();
            graph.get(u-1).add(new Node(v-1, w));
        }

        dijkstra(K-1);

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

시간 복잡도 분석

---

• 문제 조건
  • 시간 제한: 1초
  • 1 ≤ V ≤ 20,000
    1 ≤ E ≤ 300,000
• 힙(우선순위 큐)기반 다익스트라 알고리즘: O(ElogV)
  • 대략, O(300,000 X 14) = O(4200000)
  • n으로 구성된 O( )를 계산했을 때의 값이 1억 정도면 1초 정도의 시간이 걸린다.
  • 따라서,힙기반 다익스트라 알고리즘 사용 가능