문제

백준 1916번
https://www.acmicpc.net/problem/1916

N개의 도시가 있다. 그리고 한 도시에서 출발하여 다른 도시에 도착하는 M개의 버스가 있다. 우리는 A번째 도시에서 B번째 도시까지 가는데 드는 버스 비용을 최소화 시키려고 한다. A번째 도시에서 B번째 도시까지 가는데 드는 최소비용을 출력하여라. 도시의 번호는 1부터 N까지이다.

---

생각하기

다익스트라의 첫 번째 문제인 최단경로구하기 문제에서 그냥 하나만 출력하면 되는 문제여서 어렵지 않았다.

이 문제도 그냥 다익스트라의 기초를 다루는 문제라 꼭 한번 풀어보고, 이해하는게 중요한 것 같다.

동작

이전에 풀었었던 문제와 거의 유사해서 해당 풀이의 링크를 올려놓겠다.

[Java] 백준 1753번 최단경로 with 자바 (풀이)

		while( !que.isEmpty() ) {
			Node queNode = que.poll();
			int start_nodeNum = queNode.nodeNum;
			
			if( !visit[start_nodeNum] ) {
				visit[start_nodeNum] = true;
				
				for(Node node : list.get(start_nodeNum)) {
					
					if( !visit[node.nodeNum] && dist[node.nodeNum] > (dist[start_nodeNum] + node.weight) ) {
						dist[node.nodeNum] = dist[start_nodeNum] + node.weight;
						que.offer(new Node(node.nodeNum, dist[node.nodeNum]));
					}
				}
			}
		}
		
		return dist[destination];

이전 문제에서 다른 점은
1753번 문제는 전체를 출력하지만 이번에는 해당 목적지의 dist 값만 출력하면 되기 때문에 dist[destination];를 return 값으로 넘겨주기만 하면 된다.

---

코드

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

public class Main {
	private static final int INF = Integer.MAX_VALUE / 16;
	static List<ArrayList<Node>> list;
	static int dist[];

	static int N;

	static class Node implements Comparable<Node> {
		int nodeNum;
		int weight;

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

		@Override
		public int compareTo(Node o) {
			return weight - o.weight;
		}
	} // End of Node

	public static void main(String[] args) throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st;

		N = Integer.parseInt(br.readLine()); // 도시의 개수
		int M = Integer.parseInt(br.readLine()); // 버스의 개수
		

		list = new ArrayList<>();
		dist = new int[N + 1];
		Arrays.fill(dist, INF);

		for(int i=0; i<=N; i++) {
			list.add(new ArrayList<>());
		}
		
		for(int i=0; i<M; i++) {
			st = new StringTokenizer(br.readLine());

			int s = Integer.parseInt(st.nextToken());
			int d = Integer.parseInt(st.nextToken());
			int w = Integer.parseInt(st.nextToken());

			
			list.get(s).add(new Node(d, w));
		}
		
		st = new StringTokenizer(br.readLine());
		
		int start = Integer.parseInt(st.nextToken());
		int destination = Integer.parseInt(st.nextToken());
			
		System.out.println(dijkstra(start, destination));

	} // End of main

	static int dijkstra(int start, int destination) {
		PriorityQueue<Node> que = new PriorityQueue<Node>();
		boolean visit[] = new boolean[N + 1];

		dist[start] = 0;
		que.offer(new Node(start, 0));
		
		while( !que.isEmpty() ) {
			Node queNode = que.poll();
			int start_nodeNum = queNode.nodeNum;
			
			if( !visit[start_nodeNum] ) {
				visit[start_nodeNum] = true;
				
				for(Node node : list.get(start_nodeNum)) {
					
					if( !visit[node.nodeNum] && dist[node.nodeNum] > (dist[start_nodeNum] + node.weight) ) {
						dist[node.nodeNum] = dist[start_nodeNum] + node.weight;
						que.offer(new Node(node.nodeNum, dist[node.nodeNum]));
					}
				}
			}
		}
		
		return dist[destination];
	} // End of dijkstra

} // End of Main class