[백준 11779: JAVA] 최소비용 구하기 2 / 다익스트라, 역추적

개요

 

기본적인 최단거리 문제에서 경로 추적이 포함되어 있는 문제이다.

경로의 가중치가 양수이기 때문에 다익스트라를 선택하였고

경로 추적을 위해 부모 노드를 저장하여 풀이하였다.

다익스트라를 잘 모른다면  아래의 문제를 먼저 심도 있게 풀어보는 것이 좋을 것 같다.

 

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

1753번: 최단경로

풀이는 아래 게시글에 잘 설명이 되어 있다.

2020/02/09 - [알고리즘/백준] - [백준 1753 : JAVA] 최단경로 / 다익스트라

[백준 1753 : JAVA] 최단경로 / 다익스트라

 

문제

 

n(1≤n≤1,000)개의 도시가 있다. 그리고 한 도시에서 출발하여 다른 도시에 도착하는 m(1≤m≤100,000)개의 버스가 있다. 우리는 A번째 도시에서 B번째 도시까지 가는데 드는 버스 비용을 최소화 시키려고 한다. 그러면 A번째 도시에서 B번째 도시 까지 가는데 드는 최소비용과 경로를 출력하여라. 항상 시작점에서 도착점으로의 경로가 존재한다.

 

입력

 

코드

 

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

class Bus implements Comparable<Bus>{
    int end;
    int cost;

    public Bus(int end, int cost) {
        this.end = end;
        this.cost = cost;
    }

    @Override
    public int compareTo(Bus o) {
        return cost - o.cost;
    }
}
public class Main {
    static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    static BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
    // 최단거리의 최댓 값
    // 최대 노드 수 * 버스 최대 비용
    static int INF = 1_000 * 100_000;
    static ArrayList<Bus> busList[];
    static int dist[];
    static int start, end;
    static int n, m;
    static int parent[];
    static int cityCnt;
    static StringBuilder sb = new StringBuilder();

    public static void main(String[] args) throws IOException {
        n = Integer.parseInt(br.readLine());
        m = Integer.parseInt(br.readLine());

        busList = new ArrayList[n + 1];

        // 인접리스트 초기화
        for(int i = 1 ; i <= n; i++){
            busList[i] = new ArrayList<>();
        }

        // 인접리스트 초기화
        for(int i = 0 ; i < m; i++){
            StringTokenizer st = new StringTokenizer(br.readLine());

            int start = Integer.parseInt(st.nextToken());
            int end = Integer.parseInt(st.nextToken());
            int cost = Integer.parseInt(st.nextToken());

            busList[start].add(new Bus(end, cost));
        }

        StringTokenizer st = new StringTokenizer(br.readLine());

        start = Integer.parseInt(st.nextToken());
        end = Integer.parseInt(st.nextToken());

        // 최단경로를 저장한다.
        dist = new int[n + 1];
        // 경로 추적을 위한 부모노드 정보를 저장한다.
        parent = new int[n + 1];
        Arrays.fill(dist, INF);

        // 다익스트라를 이용하여 최단거리를 구한다.
        dijkstra();
        Stack<Integer> stack = searchPath();

        while(!stack.isEmpty()){
            int city = stack.pop();
            sb.append(city + " ");
        }

        bw.write(dist[end] + "\n");
        bw.write(cityCnt + "\n");
        bw.write(sb.toString());

        bw.close();
        br.close();
    }

    public static void dijkstra(){
        PriorityQueue<Bus> pq = new PriorityQueue<>();
        boolean check[] = new boolean[n + 1];

        pq.add(new Bus(start, 0));
        dist[start] = 0;

        while(!pq.isEmpty()){
            Bus curBus = pq.poll();
            int cur = curBus.end;

            if(check[cur] == true) continue;
            check[cur] = true;

            for(Bus bus : busList[cur]){
                if(dist[bus.end] > dist[cur] + bus.cost){
                    dist[bus.end] = dist[cur] + bus.cost;
                    pq.add(new Bus(bus.end, dist[bus.end]));

                    parent[bus.end] = cur;
                }
            }
        }
    }

    public static Stack<Integer> searchPath(){
        Stack<Integer> stack = new Stack<>();
        int cur = end;

        while(cur != start) {
            stack.push(cur);
            cityCnt++;

            cur = parent[cur];
        }
        stack.push(cur);
        cityCnt++;

        return stack;
    }
}