[JAVA] 백준 11779 : 최소비용 구하기 2

문제

11779번: 최소비용 구하기 2

해결 방법

다익스트라를 사용해야하는 문제이다.

다익스트라 문제를 여러 개 풀어보는 중인데 조금 생각이 필요한 문제라 괜찮은 것 같다.

경로는 인접리스트를 통해 입력해 주었고, Bus 클래스를 비용이 적은 순서대로 정렬한 뒤

우선순위큐를 사용해서 다익스트라를 구현하였다.

 

이 문제에서는 총 방문한 도시의 개수와 방문한 도시를 순서대로 출력을 해야하는 부분이 존재하는데,

그래서 그 전에 방문하였던 도시를 저장할 배열이 필요하다. 나는 root 라는 이름의 배열을 사용하였다.

 

문제에서 주어진 시작점에 해당하는 곳의 그 전 도시는 0으로 지정한 뒤에 (즉, root[시작점] = 0)

최종 목적지에 도달하였을 때 역으로 root 배열을 추적해서 ArrayList에 저장한다.

이렇게 되면 ArrayList의 크기가 총 방문한 도시의 개수가 되고, ArrayList 안에 담겨있는 내용이 

역추적을 한 도시의 경로가 되기 때문에 역으로 출력을 해주면 방문하였던 도시를 순서대로 출력할 수 있다.

 

예제 입력 코드와 예제 출력을 보면 문제에서는 1 -> 3 -> 5 가 최소 비용 경로로 나오는데 같은 입력에서

1 -> 4 -> 5 도 최소 비용 경로가 되기 때문에 아래와 같이 출력된다고 해도 제출은 문제 없다.

 

코드

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.PriorityQueue;
import java.util.StringTokenizer;
import java.io.IOException;

public class Main {

	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		int n = Integer.parseInt(br.readLine());
		int m = Integer.parseInt(br.readLine());
		
		ArrayList<Bus>[] list = new ArrayList[n + 1];
		for (int i = 1; i <= n; i++) {
			list[i] = new ArrayList<>();
		}
		
		StringTokenizer st;
		for (int i = 0; i < m; i++) {
			st = new StringTokenizer(br.readLine(), " ");
			int start = Integer.parseInt(st.nextToken());
			int dest = Integer.parseInt(st.nextToken());
			int cost = Integer.parseInt(st.nextToken());
			
			list[start].add(new Bus(dest, cost));
		}
		
		st = new StringTokenizer(br.readLine(), " ");
		int sPoint = Integer.parseInt(st.nextToken());
		int dPoint = Integer.parseInt(st.nextToken());
		
		int[] root = new int[n + 1]; // 경로를 찾기 위해 사용
		int[] temp = new int[n + 1]; // cost 저장위한 용도
		Arrays.fill(temp, Integer.MAX_VALUE);
		// 다익스트라 구현 위해 초기값 설정
		
		PriorityQueue<Bus> q = new PriorityQueue<>();
		temp[sPoint] = 0;
		root[sPoint] = 0;
		q.offer(new Bus(sPoint, 0));
		
		StringBuilder sb = new StringBuilder();
		while (!q.isEmpty()) {
			Bus bus = q.poll();
			if (bus.dest == dPoint) {
            	// 우선순위큐를 사용하기 때문에
                // 최소비용의 경로가 제일 먼저 도착
                // 그래서 바로 break로 반복문을 탈출 해도 무관하다.
				break;
			}
			
			
			for (int i = 0; i < list[bus.dest].size(); i++) {
				int dest = list[bus.dest].get(i).dest;
				int cost = list[bus.dest].get(i).cost;
				
				// 목적지까지 현재까지 탐색한 값들의 비용이
				// 지금 탐색 중인 값보다 크다면
				// 더 작은 값으로 초기화 해줌.
				if (temp[dest] > temp[bus.dest] + cost) {
					temp[dest] = temp[bus.dest] + cost;
					q.offer(new Bus(dest, temp[dest]));
					root[dest] = bus.dest;
				}
				
			}
		}
		
		sb.append(temp[dPoint] + "\n"); // 도착지점까지의 최소 비용
		
		ArrayList<Integer> route = new ArrayList<>();
		int find = dPoint;
		while (find != 0) {
			route.add(find);
			find = root[find];
		}
		// 배열을 역으로 추적하여 방문한 경로 탐색
		
		sb.append(route.size() + "\n");
		// route의 크기가 현재까지 방문한 경로의 수
		
		for (int i = route.size() - 1; i >= 0; i--) {
			sb.append(route.get(i) + " ");
		}
		// 역으로 추적했기 때문에 반대방향으로 출력
		
		System.out.println(sb);	
	}
}

class Bus implements Comparable<Bus>{
	int dest;
	int cost;
	
	Bus (int dest, int cost) {
		this.dest = dest;
		this.cost = cost;
	}

	@Override
	public int compareTo(Bus o) {
		// TODO Auto-generated method stub
		return cost - o.cost;
	}
}