[BOJ] 11779. 최소비용 구하기 2 - Java

📝 문제

문제 | 백준 11779. 최소비용 구하기 2

💡 풀이 과정

⛓ 사용한 알고리즘 : 다익스트라

단방향 간선을 가진 트리에서 최소 비용 경로를 구한 후, 이를 역추적하여 전체 경로를 알아내야 하는 문제이다. 다익스트라는 큰 변형 없이 사용했고, 이후 도착지부터 경로를 역추적해가는 과정이 추가로 필요한 경우이다.

결국 다익스트라를 수행하면서 "이전에 어던 노드에서 현재 노드로 이동해왔는지"를 기록해야 하고, 이를 어떤 방식으로 기록할까 고민하다가 노드의 개수가 정해져 있고, 갱신이 자주 일어날 것 같아서 배열을 사용하기로 결정했다. 때문에 int 형 1차원 배열 prev 를 선언하여 사용했는데, 이 때 배열의 인덱스는 현재 노드를, 해당 인덱스에 기록된 정수는 이전 노드를 의미하게 된다. 즉, preve[1] 이 3이라면 이동 경로는 3 -> 1 이 되는것이다.

아래와 같이 다익스트라 알고리즘 수행 중 최소 비용을 갱신할 때 prev 배열도 함게 갱신하는 작업을 수행해줬다.

if(cost[p.to] > cost[e] + p.w) {
		cost[p.to] = cost[e]+p.w;
		prev[p.to] = e;
		pq.offer(new Point(p.to, cost[p.to]));
}

이후 경로를 역추적할 때는 도착지부터 시작하여 prev 배열을 탐색해나가면 된다. 특정 인덱스의 값이 0이 나올 때까지 탐색을 진행하면 되는데, 이는 이전 노드가 0이라는 것을 의미하고, 노드의 번호는 1번부터 시작하므로 이전 노드가 존재하지 않는 출발지 노드라는 것을 의미한다. 또한 현재 탐색의 방향이 도착지부터 출발지까지 경로를 추적하는 역방향 탐색이기 때문에 스택을 사용하여 도착지부터 지나온 노드들을 차레로 담아준 후, 마지막에 순차적으로 pop 을 수행하며 기록하는 방식을 사용할 수 있다.

 		//경로 찾기
		Stack<Integer> stack = new Stack<>();
		stack.push(to);
		int cnt = 0;
		while(prev[to]!=0) {
			stack.push(prev[to]);
			to = prev[to];
			cnt++;
		}
		cnt++;
		sb.append(cnt+"\n"); //도시 개수
		
		while(!stack.isEmpty()) {
			sb.append(stack.pop()+" ");
		}

코드

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

public class Main {
	
	static int N,M,from,to;
	
	static int[] cost, prev;
	
	static ArrayList<Point>[] list;
	
	static void dijkstra() {
		PriorityQueue<Point> pq = new PriorityQueue<>();
		pq.offer(new Point(from, 0));
		cost[from] = 0;
		
		while(!pq.isEmpty()) {
			Point tmp = pq.poll();
			int e = tmp.to;
			
			if(cost[e] < tmp.w) continue;
			
			for(Point p: list[e]) {
				if(cost[p.to] > cost[e] + p.w) {
					cost[p.to] = cost[e]+p.w;
					prev[p.to] = e;
					pq.offer(new Point(p.to, cost[p.to]));
				}
			}
		}
		
	}
	
	public static void main(String[] args) throws NumberFormatException, IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st;
		
		N = Integer.parseInt(br.readLine());
		M = Integer.parseInt(br.readLine());
		
		list = new ArrayList[N+1];
		
		for(int i=1;i<=N;i++)
			list[i] = new ArrayList<>();
		
		for(int m=0;m<M;m++) {
			st = new StringTokenizer(br.readLine());
			int s = Integer.parseInt(st.nextToken());
			int e = Integer.parseInt(st.nextToken());
			int w = Integer.parseInt(st.nextToken());
			
			list[s].add(new Point(e,w));
		}
		
		st = new StringTokenizer(br.readLine());
		from = Integer.parseInt(st.nextToken());
		to = Integer.parseInt(st.nextToken());
		//end input
		
		cost = new int[N+1];
		prev = new int[N+1];
		Arrays.fill(cost, Integer.MAX_VALUE);
		
		dijkstra();
		StringBuilder sb = new StringBuilder();
		sb.append(cost[to]+"\n"); //최단거리
		
		//경로 찾기
		Stack<Integer> stack = new Stack<>();
		stack.push(to);
		int cnt = 0;
		while(prev[to]!=0) {
			stack.push(prev[to]);
			to = prev[to];
			cnt++;
		}
		cnt++;
		sb.append(cnt+"\n"); //도시 개수
		
		while(!stack.isEmpty()) {
			sb.append(stack.pop()+" ");
		}
		
		System.out.println(sb);
		
		
		
	}
	
	static class Point implements Comparable<Point> {
		int to, w;
		
		public Point(int to, int w) {
			this.to = to;
			this.w = w;
		}
		
		@Override
		public int compareTo(Point o) {
			return this.w - o.w;
		}
	}
}