[백준 (Baekjoon)] (Java) 문제 1753

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

1753번: 최단경로

1) 접근법

V와 E의 최대 갯수가 매우 많은 점, 또한 출발지가 정해져있는 점을 고려하여 알고리즘은 Dijkstra algorithm을 사용한다.

각 vertex로의 weight를 우선순위로 사용할 것이니 Priority Queue를 사용한다.

 

2) 시간 복잡도

Priority Queue와 다익스트라 알고리즘을 쓴 경우: O(ElogV)

 

3) 공간 복잡도

Edge의 갯수는 최대 30만개이고 30만개의 id,weight 정보 (int 2개)를 저장한다. (class Node)

따라서 ArrayList<Node>[V+1] list는 총 30*8byte (int 2개) = 2.4MB이다

 

4) 이 문제로 얻은 것

다익스트라 알고리즘 구현법

Priority Queue 사용법

BufferReader & BufferWriter 사용법

StringBuilder 사용법

 

5) 코드

import java.util.*;
import java.io.*;

public class p1753{
    static BufferedReader br;
    static BufferedWriter bw;

    static int V,E,K;
    static int u,v,w;
    static int[] dist;
    static List<Node>[] list;

    static class Node implements Comparable<Node>{
        int id, weight;

        public Node(int id, int weight){
            this.id = id;
            this.weight = weight;
        }

        @Override
        public int compareTo(Node o){
            return weight - o.weight;
        }
    }
    public static void main(String[] args) throws IOException{
        br = new BufferedReader(new InputStreamReader(System.in));
        bw = new BufferedWriter(new OutputStreamWriter(System.out));

        StringTokenizer st = new StringTokenizer(br.readLine());
        V = Integer.parseInt(st.nextToken());   //정점 개수
        E = Integer.parseInt(st.nextToken());   //간선 개수
        K = Integer.parseInt(br.readLine());    //시작 정점

        //거리배열 INF로 초기화
        dist = new int[V+1];    //거리배열
        for(int i=1;i<V+1;i++){
            dist[i] = Integer.MAX_VALUE;
        }

        //리스트 초기화
        list = new ArrayList[V+1];  //인접 정점 리스트
        for(int i=1;i<V+1;i++){
            list[i] = new ArrayList<>();
        }
        for(int i=1;i<E+1;i++){
            st = new StringTokenizer(br.readLine());
            u = Integer.parseInt(st.nextToken());
            v = Integer.parseInt(st.nextToken());
            w = Integer.parseInt(st.nextToken());
            list[u].add(new Node(v,w));
        }

        //dijkstra
        dijkstra(K);

        //output
        StringBuilder sb = new StringBuilder();
        for(int i=1;i<V+1;i++){
            if(dist[i]<Integer.MAX_VALUE) sb.append(dist[i]+"\n");
            else sb.append("INF\n");
        }
        bw.write(sb.toString());
        bw.flush();
        bw.close();
        br.close();
    }

    private static void dijkstra(int start){
        PriorityQueue<Node> pq = new PriorityQueue<>();
        dist[start] = 0;
        pq.add(new Node(start,0));

        while(!pq.isEmpty()){
            Node cur = pq.poll();
            if(cur.weight > dist[cur.id]) continue; //현재 weight가 dist에 저장된 weight보다 크면 갱신할 필요가 없다.
            for(Node next:list[cur.id]){
                int nextW = next.weight+cur.weight;
                if(dist[next.id]>nextW){     //만약 dist에 저장된 next의 weight가 cur에서 next로가는 weight보다 크다면 갱신.  
                    dist[next.id] = nextW;
                    pq.add(new Node(next.id, dist[next.id]));
                }
            }
        }
    }
  
}