[BOJ 백준] 최단경로(1753) Java

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

 

문제 설명 : 

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

 

입력 : 

첫째 줄에 정점의 개수 V와 간선의 개수 E가 주어진다. (1≤V≤20,000, 1≤E≤300,000) 모든 정점에는 1부터 V까지 번호가 매겨져 있다고 가정한다. 둘째 줄에는 시작 정점의 번호 K(1≤K≤V)가 주어진다. 셋째 줄부터 E개의 줄에 걸쳐 각 간선을 나타내는 세 개의 정수 (u, v, w)가 순서대로 주어진다. 이는 u에서 v로 가는 가중치 w인 간선이 존재한다는 뜻이다. u와 v는 서로 다르며 w는 10 이하의 자연수이다. 서로 다른 두 정점 사이에 여러 개의 간선이 존재할 수도 있음에 유의한다.

 

출력 : 

첫째 줄부터 V개의 줄에 걸쳐, i번째 줄에 i번 정점으로의 최단 경로의 경로값을 출력한다. 시작점 자신은 0으로 출력하고, 경로가 존재하지 않는 경우에는 INF를 출력하면 된다.

 

예제 입력 : 

5 6
1
5 1 1
1 2 2
1 3 3
2 3 4
2 4 5
3 4 6

 

예제 출력 : 

0
2
3
7
INF

 

접근법 : 

1) 어떻게 풀 것인가?

V이 2만, E가 30만으로 제법 큰 편이다. 

정말 단순하게 V*E는 60억으로 시간초과가 발생할 것으로 예상된다.

 

즉, 적어도 LogN으로 최단경로를 찾을 수 있는 알고리즘을 활용해야하는 문제이다.

모든 목적지를 찾아야 한다는 점에서 플로이드-워셜(Floyd-Warshall)을 떠올릴수도 있으나,

 

1) 플로이드-워셜은 N이 300 이상에서 시간초과로 불가능하다 (시간복잡도 : N^3)

2) 최소한 출발지가 고정되어있기 때문에 플로이드-워셜은 불필요하다.

는 점에서 다익스트라를 활용해볼 수 있다.

 

단, 주의할 점

1) 일반 Queue를 활용하면 시간복잡도가 O(V^2 + E) 이므로 시간초과가 발생하고,

PQ를 활용한 다익스트라의 경우 시간 복잡도가 O(ElogV)이므로 통과할 것으로 보인다.

 

2) 일반적인 다익스트라는 보통 목적지를 정해놓고, 목적지에 도달하면 종료하지만,

이 문제에서는 모든 정점에 대한 최단경로를 출력해야하므로, PQ가 모두 소진될때까지 수행해야한다.

 

V의 개수가 2만으로, 목적지 1곳을 찾는 다익스트라의 일반적인 V = 10만보다 비교적 작고,

단방향 간선이므로 시간복잡도를 줄여준(PQ를 모두 소진해도 이상없도록) 문제로 보여진다.

 

2) 시간복잡도

PQ를 활용한 다익스트라의 경우 시간 복잡도가 O(ElogV).

 

추가로 시간을 정답 출력시 V 번 출력하면 최대 2만 번 출력되므로,

가능하면 StringBuilder로 모아서 출력하는게 좋아보인다.

(Java 기준 -  832ms)

 

3) 공간복잡도

ArrayList로 인접리스트를 구현한다면,

간선 30만개 인접리스트 + 2만개 배열 몇개이므로 여유있다.

30만 * 8Bytes(int 2개) 는 약 2.3MB로 여유있다.

 

4) 풀면서 놓쳤던점

특별히 없음.

 

5) 이 문제를 통해 얻어갈 것

다익스트라 기본 코드, 1개가 아닌 N개 목적지를 필요로할때 활용법.

 

Java 코드 : 

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

// 1753 최단경로
public class Main {

    static BufferedReader br;
    static BufferedWriter bw;
   
    static class Edge implements Comparable<Edge>{
    	int targetId, cost;

		public Edge(int targetId, int cost) {
			this.targetId = targetId;
			this.cost = cost;
		}

		@Override
		public int compareTo(Edge o) {
			return this.cost - o.cost;
		}
    }
    
    static int V,E,K;
    static int u,v,w;
    static int [] dist;
    static ArrayList[] adjList;
        
    public static void main(String[] args) throws Exception  {

        br = new BufferedReader(new InputStreamReader(System.in));
        bw = new BufferedWriter(new OutputStreamWriter(System.out));
        
        StringTokenizer st;
        st = new StringTokenizer(br.readLine());
        
        V = Integer.parseInt(st.nextToken());
        E = Integer.parseInt(st.nextToken());
        K = Integer.parseInt(br.readLine());
        
        // 1. 거리배열 무한대로 초기화
        dist = new int[V+1];
        for (int i=1; i<=V; i++) {
        	dist[i] = Integer.MAX_VALUE;
        }
        
        // 2. 인접리스트 초기화
        adjList = new ArrayList[V+1];
        for (int i=1; i<=V; i++) {
        	adjList[i] = new ArrayList<Edge>();
        }
        
        // 3. 방향간선 인접리스트 입력
        for (int i=1; i<=E; i++) {
        	st = new StringTokenizer(br.readLine());
        	
        	u = Integer.parseInt(st.nextToken());
        	v = Integer.parseInt(st.nextToken());
        	w = Integer.parseInt(st.nextToken());
        	
        	adjList[u].add(new Edge(v,w));
        }
        
        // 4. 출발지부터 다익스트라 진행
        dijkstra(K);
        
        // 5. 전체 출력
        StringBuilder sb = new StringBuilder();
        for (int i=1; i<=V; i++) {
        	if (dist[i] == Integer.MAX_VALUE) {
        		sb.append("INF\n");
        	}
        	else {
        		sb.append(dist[i]+"\n");
        	}
        }
        bw.write(sb.toString());
        
        bw.flush();
        bw.close();
        br.close();
    }    

    static void dijkstra(int startId) {
    	// 1. 출발지 비용은 0으로 하고 출발지를 PQ에 넣고 시작
        PriorityQueue<Edge> pq = new PriorityQueue<Edge>(); 
        dist[startId] = 0;
        pq.add(new Edge(startId,0));
        
        while(!pq.isEmpty()) {
        	Edge cur = pq.poll();
        	
        	// * 특정 목적지에 도착하는 문제였다면, 도착지 도착후 break
        	
        	// 2. 더 큰 가중치로 도착한 경우 패스
        	if (cur.cost > dist[ cur.targetId ]) continue;
        	
        	// 3. 현재 위치에 연결된 간선 탐색
        	int len = adjList[cur.targetId].size();
        	for (int i = 0; i<len; i++) {
        		Edge next = (Edge) adjList[cur.targetId ].get(i);
        		
        		// 4. cost가 더 작을때만 갱신하고 PQ에 넣기
        		if (dist[next.targetId] > cur.cost + next.cost ) {
        			dist[next.targetId] = cur.cost + next.cost;
        			pq.add(new Edge(next.targetId, dist[next.targetId]));
        		}
        	}
        	
        }
    }

}