백준 - 11779번 최소비용 구하기 2 - java

https://www.acmicpc.net/problem/11779

접근법

기본적인 다익스트라 알고리즘으로 접근함
GRAPH라는 배열에 시작지점 인덱스에 도착지와 가중치를 Node로 담아두고, 입력으로 받는 시작지점과 끝지점으로 함수 시작

dir이라는 배열을 하나 두었는데, 해당 인덱스로 도착할 때 출발했던 인덱스를 저장함. 단, 가중치가 가장 작은 경우에만 갱신하며 이는 큐에 offer할때와 같은 시점에 이루어짐

1. 우선순위 큐를 이용해야 시간초과 안뜸
2. if(weight[cur.index] < cur.weight) continue으로 현재 가중치 비교해서 건너뛰어줘야 시간을 아낌. 이 라인은 기존 다익스트라에서 해주지 않았던것 같은데
3. 최소 비용만 출력하면 weight배열값만 출력하면 되는데, 방문한 도시 순서도 필요하므로 stack을 두고 역으로 도착지부터 이동 경로를 출발지까지 push한 후 차례로 pop해서 출력하면 끝

소스

import java.util.*;
import java.io.*;
public class Main {
	static int N;
	static int M;
	static ArrayList<Node>[] GRAPH;
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());
		N = Integer.parseInt(st.nextToken());
		
		st = new StringTokenizer(br.readLine());
		M = Integer.parseInt(st.nextToken());
		
		GRAPH = new ArrayList[N+1];
		
		for(int i = 0; i < GRAPH.length; i++) {
			GRAPH[i] = new ArrayList<Node>();
		}
		
		for(int i = 0; i < M; i ++) {
			st = new StringTokenizer(br.readLine());
			int sp = Integer.parseInt(st.nextToken());
			int ep = Integer.parseInt(st.nextToken());
			int weight = Integer.parseInt(st.nextToken());
			
			GRAPH[sp].add(new Node(ep, weight));
		}
		st = new StringTokenizer(br.readLine());
		int start = Integer.parseInt(st.nextToken());
		int end = Integer.parseInt(st.nextToken());
		
		dijkstra(start, end);
	}
	static void dijkstra(int s, int e) {
		int[] weight = new int[N+1];
		int[] dir = new int[N+1];
		Arrays.fill(weight, Integer.MAX_VALUE);
		weight[s] = 0;
		PriorityQueue<Node> q = new PriorityQueue<Node>();
		q.offer(new Node(s, 0));
		
		while(!q.isEmpty()) {
			Node cur = q.poll();
			
			if(weight[cur.index] < cur.weight) continue;
			
			for(int i = 0; i < GRAPH[cur.index].size(); i++) {
				Node link = GRAPH[cur.index].get(i);
				if(weight[link.index] > cur.weight + link.weight) {
					weight[link.index] = cur.weight + link.weight;
					dir[link.index] = cur.index;
					q.offer(new Node(link.index, cur.weight + link.weight));
				}
			}
		}
		Stack<Integer> stack = new Stack<Integer>();
		int iter = e;
		while(true) {
			stack.push(iter);
			if(dir[iter] == s) {
				stack.push(s);
				break;				
			} else {
				iter = dir[iter];
			}
		}		
		
		//1. 최소비용, 2. 경로에 있는 도시 개수, 3.방문한 도시 순서(출발지 도착지 포함)
		System.out.println(weight[e]);
		System.out.println(stack.size());
		while(!stack.isEmpty()) {
			System.out.print(stack.pop() + " ");
		}
	}
}

class Node implements Comparable<Node>{
	int index;
	int weight;
	Node(int index, int weight){
		this.index = index;
		this.weight = weight;
	}
	@Override
	public int compareTo(Node o) {
		return this.weight - o.weight;
	}	
}