📝 문제

문제를 읽어보면 알겠지만

• 각 노드들이 방향성이 있다(A->B가 된다고 해서 B->A가 되는 건 아니다)
• 가중치를 가진다
• 단일 시작점에서의 최소비용을 구한다

따라서 다익스트라 알고리즘으로 푸는 것이 좋아보였습니다.
다익스트라 알고리즘의 전개 과정은 다음과 같습니다.

1. 출발점에 대해 도착점과 비용이 짝을 이루어 들어가도록 ArrayList형의 배열을 만듭니다
2. ArrayList는 배열이나 Node 클래스 형 입니다
3. 우선순위큐를 만들어서 정점의 번호(목적지)와 비용 pair를 삽입합니다
4. 우선순위 큐는 정점까지의 최소 비용을 기준으로 정렬됩니다
5. 아직 방문하지 않은 지점 중 시작점으로부터 가장 가까운 거리의 지점에 대해 탐색합니다
6. 도착점에 대해 최소 비용을 업데이트하고 우선순위 큐에 해당 도착점과 업데이트된 최소비용을 삽입합니다

위의 과정을 거치면, 어떤 한 정점으로부터 다른 정점으로까지의 최소 비용을 찾을 수 있습니다.
시작복잡도는 모든 간선에 대해 탐색을 진행하고 최악의 경우 하나의 간선을 탐색할 때마다 우선순위 큐에 정점이 삽입되고 정렬하는 작업을 거쳐야 하므로 O(ElogV)가 됩니다.

📌 코드

package Baekjoon;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;

public class BOJ1916 {

  /**
   * 방향성이 있고, 가중치가 있다 -> 다익스트라로 풀자
   */

  static int n, m;
  static ArrayList<int[]>[] road;
  static int[] pay; // 해당 정류장으로 가는 최소 비용이 담긴 배열


  public static void main(String[] args) throws IOException {
    BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    n = Integer.parseInt(br.readLine());
    m = Integer.parseInt(br.readLine());
    road = new ArrayList[n+1]; // 리스트형을 자료형으로 가지는 배열
    for(int i = 0; i < n+1; i++){
      road[i] = new ArrayList<>(); // 초기화
    }
    pay = new int[n+1];
    Arrays.fill(pay, Integer.MAX_VALUE); // 최댓값을 넣고 시작

    StringTokenizer st;
    for(int i = 0; i < m; i++){
      st = new StringTokenizer(br.readLine());
      int s = Integer.parseInt(st.nextToken());
      int e = Integer.parseInt(st.nextToken());
      int dist = Integer.parseInt(st.nextToken());
      road[s].add(new int[] {e, dist}); // 배열의 인덱스는 출발점, 각 인덱스에 도착점과 비용 삽입
    }
    st = new StringTokenizer(br.readLine());
    int start = Integer.parseInt(st.nextToken());
    int end = Integer.parseInt(st.nextToken());

    // dijkstra
    PriorityQueue<int[]> pq = new PriorityQueue<>(((o1, o2) -> Integer.compare(o1[1], o2[1]))); // 우선순위큐 : 비용이 작은 것부터 탐색
    boolean[] visited = new boolean[n+1]; // 방문여부 검사
    pq.add(new int[] {start, 0}); // add start point
    pay[start] = 0;
    while(!pq.isEmpty()){
      int[] cur = pq.poll();
      // 방문하지 않은 곳에 대해서만 추가
      if(!visited[cur[0]]){
        visited[cur[0]] = true;

        for(int[] i : road[cur[0]]){
          if(pay[i[0]] > pay[cur[0]] + i[1]){
            pay[i[0]] = pay[cur[0]] + i[1];
            pq.add(new int[] {i[0], pay[i[0]]}); // 현재 해당 칸으로 가는 최소 비용으로 삽입한다.
          }
        }
      }
    }
    System.out.println(pay[end]);
  }
}