[BaekJoon] 11779번 최소비용 구하기 2 (Java) 문제 풀이 [Gold 3]

문제

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

11779번: 최소비용 구하기 2

 

어떻게 풀 것인가?

기존의 다익스트라 알고리즘을 사용해도 무방하나, 다만 최단경로가 지나온 노드들을 보여줘야 하고, 그리고 지나온 노드들의 갯수를 보여줘야 한다.

 

이에 나는 route로 지나온 노들을 담으며, 이후에 while 문을 이용하여 routes에 정답의 경로들을 전부다 담는 로직을 세웠다.

 

출발 노드 -> 목적 노드까지는 모든 노드를 거치지 않을 수도 있지만, 다익스트라 알고리즘은 모든 노드를 탐색하기 때문이다.

 

경로를 저장해 주기 위해 새로운 route라는 배열을 생성해 주었다. route의 인덱스가 의미하는 바는 해당 인덱스 번호를 가진 노드 바로 직전에 방문한 노드를 저장하도록 하였다.

 

다익스트라 탐색을 마친 뒤, end노드 부터 거꾸로 경로를 찾아갔다. route[route[end]]... 이런식으로 반복하도록 while문을 사용하였다. 이전 노드가 더 이상 존재하지 않는다면 0일 것이다.

 

풀면서 놓쳤던점

크게는 없었다.

 

이 문제를 통해 얻어갈 것

최단경로의 깊은 이해와 응용

 

내 코드 

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;

// 백준알고리즘 11779번 최소비용 구하기2
public class Main {
    static int N, M;

    static ArrayList<Node>[] graph;

    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());

        graph = new ArrayList[N + 1];
        for (int i = 0; i <= N; i++) graph[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());

            graph[start].add(new Node(end, cost));
        }

        StringTokenizer st = new StringTokenizer(br.readLine());
        int s = Integer.parseInt(st.nextToken());
        int e = Integer.parseInt(st.nextToken());

        Dijkstra(s, e);

    }

    public static void Dijkstra(int start, int end) {
        boolean[] check = new boolean[N + 1];
        int[] dist = new int[N + 1];
        int INF = Integer.MAX_VALUE;

        Arrays.fill(dist, INF);
        dist[start] = 0;
        int[] route = new int[N + 1];
        ArrayList<Integer> routes = new ArrayList<>();
        PriorityQueue<Node> pq = new PriorityQueue<>();
        pq.offer(new Node(start, 0));

        while (!pq.isEmpty()) {
            int nowVertex = pq.poll().index;

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

            //index의 연결된 정점 비교
            for (Node next : graph[nowVertex]) {
                if (dist[next.index] > dist[nowVertex] + next.cost) {
                    dist[next.index] = dist[nowVertex] + next.cost;
                    pq.offer(new Node(next.index, dist[next.index]));
                    route[next.index] = nowVertex;
                }
            }
        }

        int current = end;
        while (current != 0) {
            routes.add(current);
            current = route[current];
        }

        System.out.println(dist[end]);
        System.out.println(routes.size());
        for (int i = routes.size() - 1; i >= 0; i--) {
            System.out.print(routes.get(i) + " ");
        }

    }
}

class Node implements Comparable<Node> {
    int index;
    int cost;

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

    @Override
    public int compareTo(Node o) {
        return Integer.compare(this.cost, o.cost);
    }
}

 

참고

X