[백준] 1916번 : 최소비용 구하기(다익스트라) - 자바[Java]

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

1916번: 최소비용 구하기

풀이

기본적인 그래프 최단거리 문제다.

그래프 최단거리 알고리즘으로는 다익스트라, 벨만포드, 플로이드-와샬이 있다.

1 <= V <= 1,000

1 <= E <= 100,000

플로이드의 시간복잡도는 O(V^3)이므로 시간초과가 발생하고, 벨만포드의 시간복잡도는 O(VE), 다익스트라는 O(ElogV)이다. 음수 간선이 없으므로 더 빠른 다익스트라 알고리즘을 사용하여 문제를 풀었다.

다익스트라 시간복잡도

 

코드

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

public class Main {
	
	static class Edge implements Comparable<Edge> {
		int v;
		int cost;
		
		public Edge(int v, int cost) {
			this.v = v;
			this.cost = cost;
		}
		
		@Override
		public int compareTo(Edge o) {
			return this.cost - o.cost;
		}
	}
    
	static int n, m;
	static ArrayList<ArrayList<Edge>> graph = new ArrayList<>();
	static int MAX_VALUE = 100000000;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        
        n = Integer.parseInt(br.readLine());
    	m = Integer.parseInt(br.readLine());
    	
    	for (int i = 0; i <= n; i++) {
    		graph.add(new ArrayList<>());
    	}
    	
    	for (int i = 0; i < m; i++) {
    		StringTokenizer st = new StringTokenizer(br.readLine());
    		int a = Integer.parseInt(st.nextToken());
        	int b = Integer.parseInt(st.nextToken());
        	int c = Integer.parseInt(st.nextToken());
        	
        	graph.get(a).add(new Edge(b, c));
    	}

    	StringTokenizer st = new StringTokenizer(br.readLine());
    	int start = Integer.parseInt(st.nextToken());
    	int end = Integer.parseInt(st.nextToken());
    	
    	int minDist = dijkstra(start, end);
    	bw.write(minDist + "");
    	
        bw.flush();
        br.close();
        bw.close();
    }
    
    static int dijkstra(int start, int end) {
    	int[] dist = new int[n+1];
    	Arrays.fill(dist, MAX_VALUE); // 중요!
    	dist[start] = 0;
    	
    	PriorityQueue<Edge> pq = new PriorityQueue<>();
    	pq.add(new Edge(start , 0));
    	
    	while (!pq.isEmpty()) {
    		Edge cur = pq.poll();
    		
    		if (cur.cost > dist[cur.v]) continue; // 중요!
    		
    		for (Edge next: graph.get(cur.v)) {
    			if (dist[next.v] > dist[cur.v]+ next.cost) {
    				dist[next.v] = dist[cur.v]+ next.cost;
    				pq.add(new Edge(next.v, dist[next.v]));
    			}
    		}
    	}
    	
    	return dist[end];
    }
}

 

참고

https://lktgt.tistory.com/20