[자바] 백준 11779 - 최소비용 구하기 2 (java)

 문제 : boj11779

---

 

필요 알고리즘 개념

• 다익스트라 (dijkstra)
  
  • 다익스트라 응용 문제이다. 기본적인 다익스트라 구현방법은 알아야 풀 수 있고, 추가로 경로를 구할 방법도 생각해봐야 한다.

※ 제 코드에서 왜 main 함수에 로직을 직접 작성하지 않았는지, 왜 Scanner를 쓰지 않고 BufferedReader를 사용했는지 등에 대해서는 '자바로 백준 풀 때의 팁 및 주의점' 글을 참고해주세요. 백준을 자바로 풀어보려고 시작하시는 분이나, 백준에서 자바로 풀 때의 팁을 원하시는 분들도 보시는걸 추천드립니다.

 

---

 

풀이

  다익스트라 공부용으로 추천하는 문제이다. 1854번 - K번째 최단 경로도 매우 추천한다.

 

  다익스트라의 진행 경로를 출력해줘야 하는 문제이다. 처음엔 좀 당황스러웟는데, 반대로 목적지부터 타고 내려온다고 생각하는걸로 좀만 생각을 바꾸니 쉽게 풀어졌다. 즉, 시작점부터 진행 경로를 파악하긴 어렵지만, 역으로 해당 노드를 향한 노드를 파악하는건 쉽다(그냥 가장 마지막에 갱신된 노드만 기록하면 된다.)

 

  일반적인 다익스트라 코드에서 경로 파악을 위해 추가된 코드에 주석을 달아두었다.

while (!pq.isEmpty()) {
    int[] tmp = pq.poll();
    int cur = tmp[0];
    int d = tmp[1];
    if (d > dist[cur]) continue;
    for (int[] edge : edges[cur]) {
        int next = edge[0];
        int nd = d + edge[1];
        if (dist[next] <= nd) continue;
        dist[next] = nd;
        parents[next] = cur;	// 자신을 향한 가장 최근의 노드 번호를 기록한다.
        pq.add(new int[]{next, nd});
    }
}

ArrayList<Integer> path = new ArrayList<>();
for (int i = e; i != 0; i = parents[i]) {	// 목적지부터 시작지점까지 역으로 내려가면서 길을 역순으로 구한다.
    path.add(i);
}
StringBuilder sb = new StringBuilder();
sb.append(dist[e]).append('\n');
sb.append(path.size()).append('\n');
for (int i = path.size()-1; i >= 0; i--)	// 다시 역순으로 출력해주면 된다.
    sb.append(path.get(i)).append(' ');

System.out.println(sb);

 

---

 

코드 : github

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.*;

public class Main {
    private void solution() throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(br.readLine());
        int m = Integer.parseInt(br.readLine());
        ArrayList<int[]>[] edges = new ArrayList[n+1];
        for (int i = 1; i <= n; i++) edges[i] = new ArrayList<>();
        while (m-->0) {
            StringTokenizer st = new StringTokenizer(br.readLine());
            int a = Integer.parseInt(st.nextToken());
            int b = Integer.parseInt(st.nextToken());
            int c = Integer.parseInt(st.nextToken());
            edges[a].add(new int[]{b,c});
        }

        StringTokenizer st = new StringTokenizer(br.readLine());
        int s = Integer.parseInt(st.nextToken());
        int e = Integer.parseInt(st.nextToken());
        int[] dist = new int[n+1];
        Arrays.fill(dist, 100000001);
        dist[s] = 0;
        int[] parents = new int[n+1];
        PriorityQueue<int[]> pq = new PriorityQueue<>(new Comparator<int[]>() {
            @Override
            public int compare(int[] o1, int[] o2) {
                return o1[1]-o2[1];
            }
        });
        pq.add(new int[]{s, 0});
        while (!pq.isEmpty()) {
            int[] tmp = pq.poll();
            int cur = tmp[0];
            int d = tmp[1];
            if (d > dist[cur]) continue;
            for (int[] edge : edges[cur]) {
                int next = edge[0];
                int nd = d + edge[1];
                if (dist[next] <= nd) continue;
                dist[next] = nd;
                parents[next] = cur;
                pq.add(new int[]{next, nd});
            }
        }

        ArrayList<Integer> path = new ArrayList<>();
        for (int i = e; i != 0; i = parents[i]) {
            path.add(i);
        }
        StringBuilder sb = new StringBuilder();
        sb.append(dist[e]).append('\n');
        sb.append(path.size()).append('\n');
        for (int i = path.size()-1; i >= 0; i--)
            sb.append(path.get(i)).append(' ');

        System.out.println(sb);
    }

    public static void main(String[] args) throws Exception {
        new Main().solution();
    }
}