백준 - 11779 최소비용 구하기 2(Java)

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

11779번: 최소비용 구하기 2

 

다익스트라(Dijkstra) 문제입니다.

시점과 종점이 주어지고 최소 비용 및 해당 경로의 크기, 경로를 출력을 요구하고 있습니다

 

기본적인 다익스트라의 기본 개념은 "돌아갈 경우가 더 비용이 적게 들 경우 돌아간다" 입니다.

비용을 1차원 int 배열에 저장시켜 계속 최소 비용을 계산해 갱신시키는 방법을 사용합니다.

최소 비용을 저장하는 1차원 int 배열은 비용에 대한 정보만 저장하기 때문에, 경로에 대한 정보를 저장할 수 없습니다.

즉, 기본적인 다익스트라를 변형시켜야 합니다.

 

간단합니다. 

비용과 경로를 저장할 수 있는 class를 정의하여 최소 비용을 저장하는 1차원 int 배열을 대체하면 됩니다.

저의 경우 Path라는 class를 만들고, 이에 비용과 경로를 저장시키도록 했습니다.

 

[구현 코드]

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

public class Main {
    private static int n, m, s, e;
    private static final int MAX = Integer.MAX_VALUE;
    private static List<List<Node>> graph;
    private static Path[] paths;

    // 문제에 주어지는 경로와 가중치를 저장
    private static class Node {
        int n, w;

        Node(int n, int w) {
            this.n = n;
            this.w = w;
        }
    }

    // 최소 비용과 경로를 저장하는 클래스
    private static class Path{
        int dis; // 최소 비용
        List<Integer> list; // 경로

        Path(int dis, List<Integer> list){
            this.dis = dis;
            this.list = list;
        }

        List<Integer> getList(){
            return list;
        }
    }

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        StringTokenizer stz;

        n = Integer.parseInt(br.readLine());
        m = Integer.parseInt(br.readLine());

        graph = new ArrayList<>();
        for (int i = 0; i < n + 1; i++) {
            graph.add(new ArrayList<>());
        }

        for (int i = 0; i < m; i++) {
            stz = new StringTokenizer(br.readLine(), " ");

            int a = Integer.parseInt(stz.nextToken());
            int b = Integer.parseInt(stz.nextToken());
            int c = Integer.parseInt(stz.nextToken());

            graph.get(a).add(new Node(b, c));
        }

        stz = new StringTokenizer(br.readLine(), " ");
        s = Integer.parseInt(stz.nextToken());
        e = Integer.parseInt(stz.nextToken());

        dijkstra();

        // 종점의 번호를 바탕으로 해당 경로에 시점을 추가시킴
        List<Integer> ansList = paths[e].getList();
        ansList.add(0, s);

        // 정답 출력
        bw.write(paths[e].dis+"\n");
        bw.write(ansList.size() + "\n");
        for (Integer el : ansList) {
            bw.write(el + " ");
        }

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

    private static void dijkstra() {
        Queue<Node> qu = new LinkedList<>();

        // 최소 비용과 경로를 저장하는 class 배열 선언
        paths = new Path[n+1];
        for(int i=0; i<n+1; i++){
            paths[i] = new Path(MAX, new ArrayList<>());
        }

        // 시점을 0으로 만듦
        paths[s] = new Path(0, new ArrayList<>());

        qu.add(new Node(s, 0));

        while (!qu.isEmpty()){
            Node cn = qu.poll();

            //각 가중치는 양의 정수이기 때문에,
            // 현재의 가중치가 저장된 최소 비용보다 크면 최소를 갱신할 수 없기 때문에 스킵.
            // 이 코드가 없으면 시간 초과 발생
            if(paths[cn.n].dis < cn.w) continue;

            // 현재 노드와 연결된 다른 노드 탐색
            for(int i=0; i<graph.get(cn.n).size(); i++){
                Node nn = graph.get(cn.n).get(i);

                // 돌아갈 경우가 더 짧을 때
                if(paths[nn.n].dis > paths[cn.n].dis + nn.w){
                    // 저장된 경로를 가져와서 새로운 경로를 추가함
                    List<Integer> nList = new ArrayList<>();
                    for (Integer integer : paths[cn.n].getList()) {
                        nList.add(integer);
                    }
                    nList.add(nn.n);

                    paths[nn.n] = new Path( paths[cn.n].dis+ nn.w, nList);
                    qu.add(new Node(nn.n, nn.w));
                }
            }
        }
    }
}