[백준] 11779번 최소비용 구하기 2 (JAVA)

문제

- n개의 도시, m개의 버스

- 버스는 한 도시에서 출발하여 다른 도시에 도착

- A번째 도시에서 B번째 도시까지 가는데 드는 최소 비용과 경로 출력

 

해결방법

다익스트라 알고리즘을 활용하여 문제를 해결하였다. 다익스트라 알고리즘에 대한 설명은 아래 포스팅을 확인하면 좋을 것 같다.

[알고리즘] 다익스트라 알고리즘 (Dijkstra Algorithm)

다익스트라 기본 코드를 활용하여 기본적인 문제 해결 틀을 잡았는데 이 문제에서는 경로도 함께 출력해야 했기 때문에 result_city를 따로 관리해 주었다. result_city라는 배열은 각 정점에 대해서 해당 정점으로 올 때 최소 비용을 가지면 이제까지 왔던 경로에 대해서 저장해 줄 수 있도록 ArrayList로 만들어주었다. dp를 활용해서 이전까지 저장되어 있던 내용들에 현재 정보까지 더하여 update 해주면서 모든 경로를 탐색하였고, 최종적으로 목적지에 도착했을 때 드는 최소 비용과 경로를 출력할 수 있도록 코드를 구성하였다.

다익스트라 기본 코드를 활용하여 해결한 문제의 해설은 아래 포스팅을 확인하면 좋을 것 같다.

[백준] 1753번 최단경로 (JAVA)

처음 단순 다익스트라 기본 코드로 문제를 해결하려했을 때, 시간초과 문제가 발생하였다. 해당 문제를 해결하기 위해서는 현재 정점에 대해서 현재 정점을 방문하는데 드는 비용이 이미 최소 비용 배열에 저장된 값보다 크다면, 해당 과정을 건너 뛸 수 있기 때문에 continue 처리를 해주어야 시간초과를 벗어날 수 있다. 

if(result_cost[now.end] < now.cost) continue;

 

코드

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

// Node class
class Node {
    int end;
    int cost;

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

public class Main {
    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringBuilder sb = new StringBuilder();

        int n = Integer.parseInt(br.readLine());        // 도시의 개수
        int m = Integer.parseInt(br.readLine());        // 버스의 개수

        List<Node>[] list = new List[n+1];			// 각 간선에 대한 정보
        boolean[] visited = new boolean[n+1];			// 각 정점에 대한 방문 여부
        List<Integer>[] result_city = new List[n+1];		// 해당 정점을 방문하기 전 방문한 정점
        int[] result_cost = new int[n+1];			// 해당 정점을 방문하기 위한 최소 비용
		
        // 초기화
        for(int i = 1; i<=n; i++) {
            list[i] = new ArrayList<>();
            result_city[i] = new ArrayList<>();
            result_cost[i] = Integer.MAX_VALUE;
        }

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

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

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

	// 다익스트라
        PriorityQueue<Node> queue = new PriorityQueue<>((o1, o2) -> o1.cost - o2.cost);
        result_city[start].add(start);		// 출발 정점에 대한 정보 저장
        result_cost[start] = 0;			// 출발 정점의 최소비용은 0
        queue.add(new Node(start, 0));		// 출발 정점 queue에 추가
		
        while (!queue.isEmpty()) {
            Node now = queue.poll();				// 현재 방문할 정점
            // 현재 방문할 정점에 가는 최소 비용이 이미 저장된 값보다 지금 방문하려고 할 때 드는 비용이 더 크다면 pass
            if(result_cost[now.end] < now.cost) continue;
            if(!visited[now.end]) visited[now.end] = true;	// 현재 방문할 정점 방문 처리
            // 현재 방문할 정점에서 이동할 수 있는 정점에 대하여 조사
            for(int i = 0; i<list[now.end].size(); i++) {
                Node next = list[now.end].get(i);		// 다음 방문할 정점
                // 다음 방문할 정점이 방문하지 않았고, 최소 비용이 든다면
                if(!visited[next.end] && now.cost + next.cost <= result_cost[next.end]) {
                    result_cost[next.end] = now.cost + next.cost;	// 비용 Update
                    result_city[next.end].clear();			// 현재까지 이동했던 좌표들에 대한 내용 clear
                    // 이제까지 이동했던 내용에 대해서 다시 update
                    for(int j = 0; j<result_city[now.end].size(); j++) {
                        result_city[next.end].add(result_city[now.end].get(j));
                    }
                    // 다음 좌표까지 update
                    result_city[next.end].add(next.end);
                    // queue에 방문할 정점 추가
                    queue.add(new Node(next.end, result_cost[next.end]));
                }
            }
        }
		
        // 출력
        sb.append(result_cost[end]).append("\n").append(result_city[end].size()).append("\n");
        for(int i = 0; i<result_city[end].size(); i++) {
            sb.append(result_city[end].get(i) + " ");
        }

        System.out.println(sb);
    }
}