• 최단 경로 : 최소 비용 구하기는 A ⇒ B까지 가는데 드는 최소 비용만 출력하면 된다. 최단 경로 문제는 모든 Node에 대한 최소 비용을 출력하는 문제이다. 하지만, Dijkstra's Algorithm에서 시작점이 주어진 순간, 시작점으로부터 모든 Node로 가는 데의 최소 시간을 모두 구한다. 따라서, 최소 비용은 arr[index] 값, 최단 경로는 arr의 모든 값을 출력하면 되는 문제이다.

---

문제 이해

N개의 도시가 존재하고, 여러 개의 (A,B,C) 쌍이 주어질 것이다.

(A,B,C) : A ⇒ B 도시로 이동할 때 C라는 비용을 들여 이동해야 한다
라는 의미를 가지고 있다.

이 때, 특정 도시 X에서 다른 도시 Y까지 가는데 드는 최소 비용을 구하는 문제이다.

---

문제 풀이

생각보다 중요한 문구가 있다.

"버스 비용은 0보다 크거나 같고"

즉, 이 문제에서 가중치는 항상 양수를 가지며, 나는 Dijkstra's Algorithm을 사용할 수 있는 최적의 환경이 된 것이다.

Dijkstra's Algorithm을 통해 모든 Node들에 대하여 도착하는 최소 시간을 구한 뒤, index를 통해 정답을 출력하면 된다.

---

코드

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

class Dest implements Comparable<Dest>{
	int to;
	int length;
	
	public Dest(int to, int length) {
		this.to = to;
		this.length = length;
	}
	
	@Override
	public int compareTo(Dest d) {
		return this.to - d.to;
	}
}

public class Main {
	static StringBuilder sb = new StringBuilder();
	static int N,M;
	static ArrayList<Dest>[] edges;
	static int[] answer; 
    // 시작 도시부터 index 도시까지 걸린 최소 시간이 저장되는 배열
	
	static void find_route(int from, int to) throws IOException {
		answer[from] = 0;

		PriorityQueue<Dest> queue = new PriorityQueue<>();
		queue.add(new Dest(from,0));
		
		while(!queue.isEmpty()) {
			Dest d = queue.poll();
			
			if(d.length != answer[d.to]) continue;
            /*
            d.length에는 X -> d.to까지 가는데 걸리는 시간이 
            저장되어 있을 것이다
            또한 answer[d.to]에는 d.to까지 가는데 걸리는 최소 시간이 
            저장되어 있을 것이다.
            아래 for문을 통해 answer[d.to]에는 
            항상 X -> d.to로 가는 최소 시간이 저장되어 있을 것이다.
            
            즉, d.length < answer[d.to]여서 answer[d.to]를 갱신하는 과정은 
            아래 반복문에서 이미 실행된 것이다.
            반대로, d.length > answer[d.to]인 경우 계산할 필요가 없기 때문에 
            무시한다
            
            따라서, d.length와 answer[d.to]가 다른 경우는 무시해버린다.
            */
            
			for(Dest tmp:edges[d.to]) {
            /*
            출발지 start -> tmp.to 도시 까지 가는데 걸리는 시간은 
            2가지 중 하나이다.
            
            현재 배열에 저장된 ans[tmp.to](=A)이거나 
            start -> d.to -> tmp.to를 거쳐 도착하는 
            answer[d.to] + tmp.length(=B)이거나
              
            B >= A라고 가정하자. 
            그렇다면 start -> d.to -> tmp.to를 거치는 것이 오히려 
            시간적으로 손해이다.
            따라서 원래 저장되어 있던 ans[tmp.to]를 도출해낸 방법으로 
            가면 될 것이다.
            즉, B의 경로로 가는 방법을 무시해버리면 된다.

            반대로 B < A라고 가정하자. 이 때는 start -> d.to -> tmp.to로 
            가는 것이 유리하다.
            즉, ans[tmp.to]를 B값으로 갱신시켜줘야 한다.
            이 부분이 중요한데, start -> tmp.to로 가는 최소 거리가 갱신되었다.
            이 경우, 우선순위 큐에 tmp.to에 대한 정보를 다시 입력하여 
            재조사해야 한다.
            즉, tmp.to에서 바로 갈 수 있는 도시들까지 걸리는 최소 시간들에 대한
            갱신이 요구된다.
            */
				if(answer[d.to]+tmp.length >= answer[tmp.to]) continue;
				answer[tmp.to] = answer[d.to]+tmp.length;
				queue.add(new Dest(tmp.to, answer[tmp.to]));
			}
		}
		
		System.out.println(answer[to]);
	}
	
	public static void main(String[] args) throws IOException {
		FastReader sc = new FastReader();
		
		N = sc.nextInt();
		M = sc.nextInt();
		
		edges = new ArrayList[N+1];
		answer = new int[N+1];
		
		for(int i =1;i<N+1;i++) {
			edges[i] = new ArrayList<>();
			answer[i] = Integer.MAX_VALUE;
		}
		
		for(int i =0;i<M;i++) {
			int a = sc.nextInt();
			int b = sc.nextInt();
			int length = sc.nextInt();
			edges[a].add(new Dest(b,length));
            // a -> b까지 바로 가는데 걸리는 비용이 length.
		}
		
		int from  =sc.nextInt();
		int to = sc.nextInt();
		
		find_route(from, to);
	}
	
	static class FastReader // 빠른 입력을 위한 클래스
}

---

결과

• 3,4,5번째 줄 틀렸습니다 : if(d.length != answer[d.to]) 구문을 통해 생략할 수 있는 계산들을 visit 배열을 통해 방문했는지 여부를 통해 생략하려고 했다가 틀렸다. 실제로 한 번 방문했지만 알고보니 다른 방법이 좋아 새롭게 갱신되는 경우가 존재하므로 visit 배열을 활용하는 것은 처음 생각했던 방법은 좋지 않은 방법 같다.