[Java] 백준 / 최소비용 구하기 2 / 11779

[Java] 백준 / 최소비용 구하기 2 / 11779

문제

문제 링크

접근 방식

다익스트라 알고리즘으로 시작점과 끝점 사이의 최소 거리를 구한다

1. 다익스트라 알고리즘 내에 현재 점을 거치는 다음 점의 최소거리를 갱신할 때 다음 점의 이전 점을 저장하는 preVertex 배열을 생성하여 해당 배열에 최소경로의 현재 점 바로 이전 점을 저장한다
2. 최소 cost를 구하고 끝 점에서 시작 점으로 역 탐색하여 최소 경로로 거친 정점의 개수와 해당 정점 번호를 출력한다

코드

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_11779 {

	
	public static class Vertex implements Comparable<Vertex>{
		int no;
		int w;
		
		Vertex(int no,int w){
			super();
			this.no = no;
			this.w = w;
		}

		@Override
		public int compareTo(Vertex o) {
			return this.w - o.w;
		}
		
		
	}
	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<ArrayList<Vertex>> list = new ArrayList<>();
		for(int i=0;i<=n;i++) {
			list.add(new ArrayList<>());
		}
		
		for(int i=0;i<m;i++) {
			StringTokenizer st = new StringTokenizer(br.readLine());
			int v1 = Integer.parseInt(st.nextToken());
			int v2 = Integer.parseInt(st.nextToken());
			int cost = Integer.parseInt(st.nextToken());
			
			list.get(v1).add(new Vertex(v2,cost));
		}
		
		StringTokenizer st = new StringTokenizer(br.readLine());
		
		int start = Integer.parseInt(st.nextToken());
		int end = Integer.parseInt(st.nextToken());
		
		int[] distance = new int[n+1];
		boolean[] visited = new boolean[n+1];
		int[] preVertex = new int[n+1];
		
		Arrays.fill(distance, Integer.MAX_VALUE);
		Arrays.fill(preVertex, -1);
		
		distance[start] = 0;
		
		PriorityQueue<Vertex> pq = new PriorityQueue<>();
		pq.offer(new Vertex(start,distance[start]));
		
		while(!pq.isEmpty()) {
			int current = pq.poll().no;
			
			if(visited[current]) continue;
			visited[current] = true;
			
			
			if(current == end) break;
			
			for(Vertex v : list.get(current)) {
				if(distance[v.no] > distance[current] + v.w ) {
					distance[v.no] = distance[current] + v.w;
					preVertex[v.no]= current;
					pq.offer(new Vertex(v.no, distance[v.no]));
				}
			}
		}
		
		Stack<Integer> stack = new Stack<>();
		int city = end;
		
		while(city != -1) {
			stack.push(city);
			city = preVertex[city];
		}
		
		StringBuilder sb = new StringBuilder();
		int size = stack.size();
		
		sb.append(distance[end]).append("\n");
		sb.append(size).append("\n");
		for(int i=0;i<size;i++) {
			sb.append(stack.pop()).append(" ");
		}
		sb.setLength(sb.length()-1);
		
		System.out.println(sb);
		
	}

}