[BOJ/Dijkstra] 백준 1916 - 최소비용 구하기 / 11779 - 최소비용 구하기 2 (Java)

1916 - 최소비용 구하기

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

문제

N개의 도시/ 한 도시에서 출발해서 다른 도시에 도착하는 M개의 버스
A번째 도시에서 B번째 도시까지 가는데 드는 비용 최소화

입력
첫째 줄: 도시 개수 N (1 <= N <= 1,000)
둘째 줄: 버스 개수 M (1 <= M <= 100,000)
셋째 줄 ~ M+2줄: 출발지, 도착지, 비용 (0  <= 비용 <= 100,000)
M+3줄: 구하고자 하는 구간 출발지, 도착지
출력: 출발 도시에서 도착 도시까지 가는데 드는 최소 비용

---

코드

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

// 최소비용 구하기
public class boj_1916 {
    static class Node implements Comparable<Node> {
        int to, cost;

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

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

    static int N, M;
    static List<List<Node>> graph;

    static int dijkstra(int start, int end) {
        int[] dist = new int[N + 1];
        Arrays.fill(dist, Integer.MAX_VALUE);
        dist[start] = 0;

        Queue<Node> pQ = new PriorityQueue<>();
        pQ.offer(new Node(start, 0));

        while (!pQ.isEmpty()) {
            Node cur = pQ.poll();

            if (cur.cost > dist[cur.to]) continue;

            for (Node next : graph.get(cur.to)) {
                int newCost = cur.cost + next.cost;
                if (newCost < dist[next.to]) {
                    dist[next.to] = newCost;
                    pQ.offer(new Node(next.to, newCost));
                }
            }
        }

        return dist[end];
    }

    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<>();
        for (int i = 0; i <= N; i++) {
            graph.add(new ArrayList<>());
        }

        for (int i = 0; i < M; i++) {
            StringTokenizer st = new StringTokenizer(br.readLine());
            int startCity = Integer.parseInt(st.nextToken());
            int endCity = Integer.parseInt(st.nextToken());
            int cost = Integer.parseInt(st.nextToken());

            graph.get(startCity).add(new Node(endCity, cost));
        }

        StringTokenizer st = new StringTokenizer(br.readLine());
        int start = Integer.parseInt(st.nextToken());
        int end = Integer.parseInt(st.nextToken());

        System.out.println(dijkstra(start, end));
    }
}

---

11779 - 최소비용 구하기 2

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

문제

N개의 도시/ 한 도시에서 출발해서 다른 도시에 도착하는 M개의 버스
A번째 도시에서 B번째 도시까지 가는데 드는 비용 최소화

입력
첫째 줄: 도시 개수 N (1 <= N <= 1,000)
둘째 줄: 버스 개수 M (1 <= M <= 100,000)
셋째 줄 ~ M+2줄: 출발지, 도착지, 비용 (0  <= 비용 <= 100,000)
M+3줄: 구하고자 하는 구간 출발지, 도착지
출력
첫째 줄: 출발 도시에서 도착 도시까지 가는데 드는 최소 비용
둘째 줄: 최소 비용 갖는 경로에 포함돼 있는 도시 개수(출발지, 도착지 포함)
셋째 줄: 최소 비용 갖는 경로를 방문하는 도시 순서대로

---

풀이

• 도착지에서 `parent[]`따라 거꾸로 거슬러 올라가서 리스트에 저장하고 `reverse()`로 정상 순서 만들기
  • `parent[]`: 최단 경로 갱신될 때마다 직전 노드 저장하는 배열

if (nextCost < dist[next.to]) {
    dist[next.to] = nextCost;
    parent[next.to] = cur.to;  // 경로 저장
    pQ.offer(new Node(next.to, nextCost));
}

 

 

int[] dist = dijkstra(start);
sb.append(dist[end]).append("\n");

List<Integer> path = new ArrayList<>();
int node = end;

while (node != -1) {
    path.add(node);
    node = parent[node];
}

Collections.reverse(path);

sb.append(path.size()).append("\n");

for (int p : path) sb.append(p).append(" ");

---

코드

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

// 최소비용 구하기 2
public class boj_11779 {
    static class Node implements Comparable<Node> {
        int to, cost;

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

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

    static int n, m;
    static List<List<Node>> graph;
    static final int INF = Integer.MAX_VALUE;
    static int[] parent;

    static int[] dijkstra(int start) {
        int[] dist = new int[n + 1];
        Arrays.fill(dist, INF);
        dist[start] = 0;

        parent = new int[n + 1];
        Arrays.fill(parent, -1);

        PriorityQueue<Node> pQ = new PriorityQueue<>();
        pQ.offer(new Node(start, 0));

        while (!pQ.isEmpty()) {
            Node cur = pQ.poll();

            if (cur.cost > dist[cur.to]) continue;

            for (Node next : graph.get(cur.to)) {
                int nextCost = dist[cur.to] + next.cost;

                if (nextCost < dist[next.to]) {
                    dist[next.to] = nextCost;
                    parent[next.to] = cur.to;
                    pQ.offer(new Node(next.to, nextCost));
                }
            }
        }

        return dist;
    }

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringBuilder sb = new StringBuilder();
        StringTokenizer st;

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

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

        while (m-- > 0) {
            st = new StringTokenizer(br.readLine());
            int a = Integer.parseInt(st.nextToken());
            int b = Integer.parseInt(st.nextToken());
            int c = Integer.parseInt(st.nextToken());

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

        st = new StringTokenizer(br.readLine());
        int start = Integer.parseInt(st.nextToken());
        int end = Integer.parseInt(st.nextToken());

        int[] dist = dijkstra(start);
        sb.append(dist[end]).append("\n");


        List<Integer> path = new ArrayList<>();
        int node = end;

        while (node != -1) {
            path.add(node);
            node = parent[node];
        }

        Collections.reverse(path);

        sb.append(path.size()).append("\n");

        for (int p : path) sb.append(p).append(" ");

        System.out.println(sb);
    }
}