[백준 11779] 최소비용 구하기2 (Java) - 다익스트라

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

최소비용 구하기 2

문제

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

입력

첫째 줄에 도시의 개수 n(1≤n≤1,000)이 주어지고 둘째 줄에는 버스의 개수 m(1≤m≤100,000)이 주어진다. 그리고 셋째 줄부터 m+2줄까지 다음과 같은 버스의 정보가 주어진다. 먼저 처음에는 그 버스의 출발 도시의 번호가 주어진다. 그리고 그 다음에는 도착지의 도시 번호가 주어지고 또 그 버스 비용이 주어진다. 버스 비용은 0보다 크거나 같고, 100,000보다 작은 정수이다.

그리고 m+3째 줄에는 우리가 구하고자 하는 구간 출발점의 도시번호와 도착점의 도시번호가 주어진다.

출력

첫째 줄에 출발 도시에서 도착 도시까지 가는데 드는 최소 비용을 출력한다.

둘째 줄에는 그러한 최소 비용을 갖는 경로에 포함되어있는 도시의 개수를 출력한다. 출발 도시와 도착 도시도 포함한다.

셋째 줄에는 최소 비용을 갖는 경로를 방문하는 도시 순서대로 출력한다. 경로가 여러가지인 경우 아무거나 하나 출력한다.

예제 입력 1 복사

5
8
1 2 2
1 3 3
1 4 1
1 5 10
2 4 2
3 4 1
3 5 1
4 5 3
1 5

예제 출력 1 복사

4
3
1 3  

---

풀이

전체코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.PriorityQueue;
import java.util.StringTokenizer;

public class Main {
    static int N,M;
    static ArrayList<City2>[] A;
    static int[] costs;
    static int[] previous;
    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()); // 버스노선 개수
        A = new ArrayList[N+1]; // 도시번호 1부터 시작
        costs = new int[N+1]; // 최소비용 저장 배열
        previous = new int[N+1]; // 최소비용 업데이트 시 이전경로 저장

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

        // 노선정보 입력받기
        StringTokenizer st;
        for(int i=0; i<M; i++){
            st = new StringTokenizer(br.readLine());
            int start = Integer.parseInt(st.nextToken()); // 출발도시
            int end = Integer.parseInt(st.nextToken()); // 도착도시
            int cost = Integer.parseInt(st.nextToken()); // 비용

            A[start].add(new City2(end, cost)); // 단방향 노선
        }

        // 목표 출발, 도착 도시 입력받기
        st = new StringTokenizer(br.readLine());
        int start = Integer.parseInt(st.nextToken());
        int end = Integer.parseInt(st.nextToken());

        // 시작노드는 이전 노드없음
        previous[start] = -1;

        // 최소비용 배열 초기화
        int INF = 100000001;
        Arrays.fill(costs, INF);
        costs[start] = 0; // 출발도시는 최소거리 0

        dijkstra(start);

        ArrayList<Integer> route = new ArrayList<>();
        route.add(end);
        int prev = previous[end];
        while (prev != -1){
            route.add(prev);
            prev = previous[prev];
        }

        StringBuilder sb = new StringBuilder();
        sb.append(costs[end] + "\n");
        sb.append(route.size() + "\n");

        for (int i=route.size()-1; i>=0; i--){
            sb.append(route.get(i)+" ");
        }

        System.out.println(sb);

    }
    private static void dijkstra(int start){
        PriorityQueue<City2> pq = new PriorityQueue<>();
        pq.offer(new City2(start, 0));

        while (!pq.isEmpty()){
            City2 now = pq.poll();

            // 현재 최소비용이 이미 더 작다면 무시
            if (now.cost > costs[now.index]) continue;

            for(City2 next : A[now.index]){
                // 새로 탐색한 경로가 비용이 더 작다면 update
                int newCost = costs[now.index] + next.cost;
                if (newCost < costs[next.index]){
                    costs[next.index] = newCost;
                    previous[next.index] = now.index; // 최소비용 업데이트 시 이전노드 기록
                    pq.offer(new City2(next.index, newCost));
                }
            }
        }
    }
}
class City2 implements Comparable<City2>{
    int index; // 도착 도시 번호
    int cost; // 비용

    public City2(int index, int cost){
        this.index = index;
        this.cost = cost;
    }

    @Override
    public int compareTo(City2 other) {
        return this.cost - other.cost; // 비용 오름차순
    }
}

• 다익스트라를 활용한 문제
• 최소비용을 구하는 것까지는 다익스트라로 해결이 가능한데, 경로를 기록하는 것이 관건인 문제

City2 클래스 선언

이미 City라는 클래스를 선언해둔 것이 패키지 내에 있어서, 그냥 City2로 정의하였다.

최소비용을 구하는 것이므로, Comparable을 implements 해준 뒤, cost 오름차순으로 정렬해주었다.

class City2 implements Comparable<City2>{
    int index; // 도착 도시 번호
    int cost; // 비용

    public City2(int index, int cost){
        this.index = index;
        this.cost = cost;
    }

    @Override
    public int compareTo(City2 other) {
        return this.cost - other.cost; // 비용 오름차순
    }
}

 

다익스트라 수행

private static void dijkstra(int start){
        PriorityQueue<City2> pq = new PriorityQueue<>();
        pq.offer(new City2(start, 0));

        while (!pq.isEmpty()){
            City2 now = pq.poll();

            // 현재 최소비용이 이미 더 작다면 무시
            if (now.cost > costs[now.index]) continue;

            for(City2 next : A[now.index]){
                // 새로 탐색한 경로가 비용이 더 작다면 update
                int newCost = costs[now.index] + next.cost;
                if (newCost < costs[next.index]){
                    costs[next.index] = newCost;
                    previous[next.index] = now.index; // 최소비용 업데이트 시 이전노드 기록
                    pq.offer(new City2(next.index, newCost));
                }
            }
        }
    }

• 출발노드를 pq에 넣고 큐가 빌 동안 아래 동작을 반복수행한다.
  • pq에서 poll하여 now(City2)를 뽑아낸다.
  • 현재 최소비용이 이미 더 작다면 (now.cost < costs[now.inex]) continue한다. 
  • now.index의 인접노드리스트 A를 순회하면서 새로운 경로를 탐색한 것이 더 작다면, costs[next.index]에 update 후
  • previous[next.index] = now.index를 입력하여 이전 노드를 기록한다.
  • pq에 City(next.index, newCost)를 다시 넣는다.

previous 배열로 경로 출력하기

       // 시작노드는 이전 노드없음
        previous[start] = -1;
        
        dijkstra(start);

        ArrayList<Integer> route = new ArrayList<>();
        route.add(end);
        int prev = previous[end];
        while (prev != -1){
            route.add(prev);
            prev = previous[prev];
        }

        StringBuilder sb = new StringBuilder();
        sb.append(costs[end] + "\n");
        sb.append(route.size() + "\n");

        for (int i=route.size()-1; i>=0; i--){
            sb.append(route.get(i)+" ");
        }

        System.out.println(sb);

• 시작노드의 이전노드는 없으므로 -1로 초기화해준다.
• 다익스트라 수행 후, previous 배열의 도착노드 -> 출발노드로 다시 회귀하며 경로를 기록해간다.
• route리스트를 다시 역순으로 출력해준다.