[BOJ/Gold3] 11779번 최소비용 구하기 2 - JAVA[자바]

난이도 : 골드 3

유형 : 최단 경로 / 다익스트라

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

구현 시간 : 30분

 

 

 

 

문제풀이

해당 문제를 해결하기 위해서 다익스트라 알고리즘을 사용하여 출발 도시에서 각 노드(도시)까지의 최소 시간을 구하고, 동시에 이전 방문 노드를 저장해야 한다.

 

이를 위해 인접한 노드를 방문하며 최소 시간을 distance[] 배열에 갱신하고, 이와 함께 이전 노드를 preN[] 배열에 저장한다.

이렇게 하면 특정 노드에 도달했을 때 해당 노드로 오기까지의 이전 노드를 추적할 수 있다.

이후 최단 거리를 출력하고, Stack을 사용하여 방문 순서를 역순으로 출력한다.

 

핵심은 다익스트라 알고리즘에서 distance[] 배열을 갱신할 때, 이전 노드를 preN[] 배열에 함께 기록하여 경로 추적이 가능하다는 것을 이해하는게 중요하다.

 

 

 

1차 시도 - 통과

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
import java.util.PriorityQueue;
import java.util.Stack;
import java.util.StringTokenizer;
public class Main {

    static StringTokenizer st;
    static int N;
    static int M;
    
    static int start;
    static int end;
    
    static int[] distance, preN;
    static List<Node>[] list;
    
    static class Node implements Comparable<Node> {
        int idx;
        int cost;
        
        public Node(int idx, int cost) {
            this.idx = idx;
            this.cost = cost;
        }
        
        @Override
        public int compareTo(Node o) {
            return Integer.compare(cost, o.cost);
        }
    }
    
    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());
        
        distance = new int[N + 1];      // 노드 별 최소 거리 저장
        preN = new int[N + 1];          // 이전 방문 노드 저장
        list = new List[N + 1];         // 노드 연결, 비용 정보 저장
        Arrays.fill(distance, Integer.MAX_VALUE);
        
        for (int i = 1; i < N + 1; i++) {
            list[i] = new ArrayList<>();
        }
        for (int i = 0; i < M; i++) {
            st = new StringTokenizer(br.readLine());
            int from = Integer.parseInt(st.nextToken());
            int to = Integer.parseInt(st.nextToken());
            int cost = Integer.parseInt(st.nextToken());
            list[from].add(new Node(to, cost));
        }
        
        st = new StringTokenizer(br.readLine());
        start = Integer.parseInt(st.nextToken());
        end = Integer.parseInt(st.nextToken());
        
        dijkstra();
        System.out.println(distance[end]);
        
        // 역추적 시작
        Stack<Integer> stack = new Stack<>();
        stack.push(end);
        int cnt = 1;
        
        while (preN[end] != 0) {
            cnt++;
            stack.push(preN[end]);
            end = preN[end];
        }
        
        System.out.println(cnt);
        
        while (!stack.isEmpty()) {
            System.out.print(stack.pop() + " ");
        }
    }
    
    public static void dijkstra() {
        PriorityQueue<Node> pq = new PriorityQueue<>();
        pq.offer(new Node(start, 0));
        distance[start] = 0;
        
        while(!pq.isEmpty()) {
            Node node = pq.poll();
            int idx = node.idx;
            int cost = node.cost;
            
            if (cost > distance[idx]) {
                continue;
            }
            
            for (Node next : list[idx]) {
                int nextIdx = next.idx;
                int newCost = cost + next.cost;
                
                if (distance[nextIdx] > newCost) {
                    distance[nextIdx] = newCost;
                    pq.offer(new Node(nextIdx, newCost));
                    // 이전 방문 노드 추가
                    preN[nextIdx] = idx;
                }
            }
        }
    }
}