BOJ_11779 : 최소비용 구하기 2

👉 문제링크

11779번: 최소비용 구하기 2

---

---

🔸 문제 분석 🔸

• n개의 노드와 m개의 단방향 간선 정보가 주어진다.
• 시작 노드부터 목적지 노드까지의 경로 중 비용이 최소값이 되는 경로를 찾아, 비용과 경로 상의 노드 수 및 경로를 출력한다.
  • 같은 최소값이면서 다른 경로일 수 있는데, 모두 정답으로 인정된다.

🔸 문제 풀이 🔸

• 다익스트라 알고리즘으로 최단경로를 구한다.
• 비용의 최소값 뿐만 아니라 최단경로를 출력해야 하므로, 값이 경신될 때 이전 출발 노드의 번호를 저장한다.
• 모든 계산 이후, 최종 목적지 노드부터 시작 노드로 역행하며 경로를 탐색한다.
• 최소 비용, 경로 상의 노드 수, 경로를 출력한다.

🔸 코드 🔸

import java.io.*;
import java.util.ArrayList;
import java.util.PriorityQueue;
import java.util.Stack;
import java.util.StringTokenizer;

public class Main {
    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 st = null;
        StringBuilder sb = new StringBuilder();

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

        ArrayList<Edge>[] adjlist = new ArrayList[n + 1];
        Edge[] node = new Edge[n + 1];

        for (int i = 1; i <= n; i++) {
            node[i] = new Edge(0, i, Integer.MAX_VALUE);
            adjlist[i] = new ArrayList<>();
        }

        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());
            adjlist[start].add(new Edge(start, end, cost));
        }

        st = new StringTokenizer(br.readLine());
        int first = Integer.parseInt(st.nextToken());
        int last = Integer.parseInt(st.nextToken());

        PriorityQueue<Edge> pq = new PriorityQueue<>();
        pq.add(new Edge(0, first, 0));

        while (!pq.isEmpty()) {
            Edge edge = pq.poll();

            if (edge.cost < node[edge.end].cost) {
                node[edge.end] = edge;
            } else continue;

            for (Edge e : adjlist[edge.end]) {
                if (edge.cost + e.cost < node[e.end].cost) {
                    pq.add(new Edge(e.start, e.end, e.cost + edge.cost));
                }
            }
        }

        sb.append(node[last].cost).append('\n');

        int now = last;
        Stack<Integer> stack = new Stack<>();
        stack.push(now);

        while (now != first) {
            now = node[now].start;
            stack.push(now);
        }

        sb.append(stack.size()).append('\n');

        while (!stack.isEmpty()) {
            sb.append(stack.pop()).append(' ');
        }

        bw.write(sb.toString());
        bw.flush();
    }

    private static class Edge implements Comparable<Edge> {
        int start;
        int end;
        int cost;

        public Edge(int start, int end, int cost) {
            this.start = start;
            this.end = end;
            this.cost = cost;
        }

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

🔸 코드 해석 🔸

• 시작 노드, 도착 노드, 비용을 저장하고 활용할 Edge 클래스를 만들어 사용한다.
• ArrayList 배열인 adjlist에 노드 별 경로를 Edge로 입력받아 저장한다.
• 각 노드의 최소 비용은 Edge 배열인 node에 저장한다.
• 우선순위 큐에 1번노드를 넣는 것을 시작으로 다익스트라 알고리즘을 실행한다.
  • 우선순위 큐에서 나온 비용이 현재 저장된 최소값 보다 작으면, 값을 갱신한다.
  • 갱신되지 않으면 다음 원소를 확인하고, 갱신되었으면 연결된 경로를 다시 확인할 수 있도록 우선순위 큐에 넣는다.
• 모든 계산이 끝난 후, 최종으로 계산된 최소 비용, 경로 수, 경로를 출력한다.
  • 경로는 Stack에 담으며 역순회 하다가, 시작 노드를 만나면 Stack원소를 꺼내며 Stringbuilder에 담아 출력한다.

---

🔸 end 🔸

• 45번째 줄에 else continue 부분을 쓰지 않아서, 갱신되지 않은 노드도 다시 탐색하게 되었더니 시간 초과가 났다.
  • 이  효율성 부분을 생각하긴 했는데, 집중이 흐려져서 누락하고 넘어갔던 것 같다.
  • 원래 이전 노드를 저장하고, 역순회 하는 게 아니라 큐, Stringbuilder, Arraylist를 생각했다가 메모리가 터질 것 같아 고민하다 보니 집중이 흐려졌다.
  • 결과는 이전 노드 저장이라는 간단한 솔루션으로 나왔다. 그래도 다시 한번 알고리즘을 점검하는 버릇을 들이자.