[알고리즘] 백준 11779 최소비용 구하기 2 -다익스트라, 최단경로-

www.acmicpc.net/problem/11779

11779번: 최소비용 구하기 2

 

 

 

백준 다익스트라 분류 문제에 있는 최소비용 구하기 2 입니다.

지나간 도시의 개수와 경로도 출력해야하는 특징이 있는 문제였습니다. 

나머지는 원래 다익스트라 풀던대로 풀이했습니다.

 

P.S 그리고 미리 말하면 예제에서는 출력이 1 3 5 가 나오는데 제 갈 수 있는 최단경로가 여러개가 생길 수 있기 떄문에 1 4 5 도 맞습니다.

 

 

 

//역추적
        Stack<Integer> stack = new Stack<>();
        while (true) {
            stack.push(endNode);
            endNode = route[endNode];
            if (endNode == startNode) {
                stack.push(endNode);
                break;
            }
        }
        while (!stack.isEmpty()) {
            System.out.print(stack.pop() + " ");
        }

while (!queue.isEmpty()) {
            Node node = queue.poll();
            int vertex = node.vertex;
            int weight = node.weight;
            if (vertex == endNode) break;
            if (distance[vertex] < weight) continue;
            for (int i = 0; i < nodeList[vertex].size(); i++) {
                int nextVertex = nodeList[vertex].get(i).vertex;
                int nextWeight = nodeList[vertex].get(i).weight + weight;
                if (distance[nextVertex] > nextWeight) {
                    distance[nextVertex] = nextWeight;
                    route[nextVertex] = vertex; //역추적을 위한 배열
                    queue.offer(new Node(nextVertex, nextWeight));
                }
            }
        }

지나간 경로를 구하기 위해서 역추적 방법을 사용했습니다.

route[] 배열을 생성하여 최단경로를 갱신할때마다 route[이후노드번호] = 이전노드번호 로 저장을 하고 나중에 도착노드 부터 역추적하여 방문과정을 구했습니다.

 

 

 

풀이는 다음과 같습니다. 

 

[Java]

import java.util.*;

class Main {
    private static int INF = Integer.MAX_VALUE;
    private static int[] distance;
    private static int[] route; //역추적을 위한
    private static ArrayList<Node>[] nodeList;
    private static int n; //도시의 개수
    private static int m; //버스의 개수

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        n = sc.nextInt();
        m = sc.nextInt();
        nodeList = new ArrayList[n + 1];
        for (int i = 1; i <= n; i++) {
            nodeList[i] = new ArrayList<>();
        }
        for (int i = 0; i < m; i++) {
            int start = sc.nextInt();
            int end = sc.nextInt();
            int weight = sc.nextInt();
            nodeList[start].add(new Node(end, weight));
        }
        int startNode = sc.nextInt();
        int endNode = sc.nextInt();
        System.out.println(dijkstra(startNode, endNode));
        //역추적
        Stack<Integer> stack = new Stack<>();
        while (true) {
            stack.push(endNode);
            endNode = route[endNode];
            if (endNode == startNode) {
                stack.push(endNode);
                break;
            }
        }
        while (!stack.isEmpty()) {
            System.out.print(stack.pop() + " ");
        }
    }

    private static int dijkstra(int startNode, int endNode) {
        route = new int[n + 1];
        distance = new int[n + 1];
        Arrays.fill(distance, INF);
        distance[startNode] = 0;
        PriorityQueue<Node> queue = new PriorityQueue<>();
        queue.add(new Node(startNode, 0));
        while (!queue.isEmpty()) {
            Node node = queue.poll();
            int vertex = node.vertex;
            int weight = node.weight;
            if (vertex == endNode) break;
            if (distance[vertex] < weight) continue;
            for (int i = 0; i < nodeList[vertex].size(); i++) {
                int nextVertex = nodeList[vertex].get(i).vertex;
                int nextWeight = nodeList[vertex].get(i).weight + weight;
                if (distance[nextVertex] > nextWeight) {
                    distance[nextVertex] = nextWeight;
                    route[nextVertex] = vertex;
                    queue.offer(new Node(nextVertex, nextWeight));
                }
            }
        }
        return distance[endNode];
    }

    private static class Node implements Comparable<Node> {
        int vertex;
        int weight;

        Node(int vertex, int weight) {
            this.vertex = vertex;
            this.weight = weight;
        }

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

 

 

 

댓글과 공감은 큰 힘이 됩니다. 감사합니다. !!