[BOJ_1753 | Dikjstra]최단경로

풀이

문제 자체는 다익스트라 알고리즘을 이용해서 한 노드에서 다른 모든 노드들에 이르는

최단 경로를 출력하면 되는 간단한 문제였다.

우선순위 큐 (Priority Queue)를 이용해서 다익스트라 알고리즘을 구현했고, 

우선순위 큐를 이용하기 위해서 

목적지 노드의 인덱스와 시작점으로부터의 거리를 저장하는 Element라는 원소 클래스를 정의하였다.

*우선순위큐를 이용한 다익스트라 알고리즘은 시간 복잡도가 O(ElogV)정도이다.

문제는 간단했으나, 문제에 걸린 제약조건이 보기보다 꽤나 까다로웠다. 

맨 처음에는 인접행렬과 Scanner를 통해 알고리즘을 수행했으나

메모리초과와 시간초과가 동시에 발생하였다.

메모리 초과 이유는 인접행렬을 사용했기 때문인데,

예를 들어 2만개의 노드가 존재한다면, Integer형을 저장하는 인접행렬의 크기는

20000*20000*4(byte)로 1.6GB에 달하는 메모리를 잡아먹게 된다.

따라서 인접행렬을 사용하는 대신에, 입력받은 간선의 개수만큼의 크기만 메모리에 할당하면 되는 

ArrayList를 사용하였다.

또한 Scanner를 이용한 인풋과 아웃풋의 처리는

우리에게 매우 익숙하기도 하고 편리한 기능들이 많아 자주 사용하지만

비교적 느린 수행시간을 가지기 때문에

BufferedReader, BufferedWriter를 사용하여 입출력을 처리하는 것이 빠르다.

소스 코드

import java.util.*;
import java.io.*;
public class BOJ_1753 {
 
    static int n, m, start;
    static final int inf = Integer.MAX_VALUE;
    static int[] dis;
    static List<Element>[] graphArr;
 
    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 = null;
        st = new StringTokenizer(br.readLine());
        n = Integer.parseInt(st.nextToken());
        m = Integer.parseInt(st.nextToken());
        start = Integer.parseInt(br.readLine())-1;
 
        dis = new int[n];
        graphArr = new ArrayList[n];
 
        //initialization
        Arrays.fill(dis, inf);
 
        for(int i=0;i<graphArr.length;i++) graphArr[i] = new ArrayList<Element>();
        for(int i=0;i<m;i++){
            st = new StringTokenizer(br.readLine());
            int i1 = Integer.parseInt(st.nextToken())-1;
            int j1 = Integer.parseInt(st.nextToken())-1;
            int val = Integer.parseInt(st.nextToken());
            graphArr[i1].add(new Element(j1, val));
        }
 
        Dikjstra(start);
 
        for(int i=0;i<n;i++){
            if(dis[i] == inf) bw.write("INF\n");
            else bw.write(dis[i]+"\n");
        }
        bw.flush();
        bw.close();
    }
 
    public static void Dikjstra(int start){
        dis[start] = 0;
        PriorityQueue<Element> q = new PriorityQueue<Element>();
        q.offer(new Element(start, dis[start]));
 
        while(!q.isEmpty()){
            int qDis = q.peek().getDis();
            int qIndex = q.peek().getIndex();
            q.poll();
 
            if(qDis > dis[qIndex]) continue;
            for(int i=0;i<graphArr[qIndex].size();i++){
                Element child = graphArr[qIndex].get(i);
                if(dis[child.getIndex()] > dis[qIndex] + child.getDis()){
                    dis[child.getIndex()] = dis[qIndex] + child.getDis();
                    q.offer(new Element(child.getIndex(), dis[child.getIndex()]));
                }
            }
        }
    }
    static class Element implements Comparable<Element>{
        private int index;
        private int dis;
        Element(int index, int dis){
            this.index = index;
            this.dis = dis;
        }
        public int getIndex(){ return index;}
        public int getDis(){return dis;}
        public int compareTo(Element obj){
            return dis <= obj.dis ? -1 : 1 ;
        }
    }
}