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

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

11779번: 최소비용 구하기 2

다익스트라 문제 bfs pq 이용해 최소비용으로 하면 다익스트라라고 하신 민O형의 말씀. 덕분에 다익스트라 방법을 까먹더라도 bfs에 pq 이용해서 푼다는 것을 기억하고 있다.

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

public class bj11779 {
	static int N,M,cityCount;
	static boolean [] visit;
	static int[] minDist,track;
	static class Edge implements Comparable<Edge>{
		int end;
		int weight;
		Edge(int e,int w){
			end = e;
			weight = w;
		}
		@Override
		public int compareTo(Edge o) {
			// TODO Auto-generated method stub
			return weight - o.weight;
		}
		
	}
	static ArrayList<ArrayList<Edge>> vertex = new ArrayList<>();
	public static void main(String[] args) throws NumberFormatException, IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		N = Integer.parseInt(br.readLine());
		M = Integer.parseInt(br.readLine());
		visit = new boolean[N+1];
		for(int n=0;n<=N;n++) {
			vertex.add(new ArrayList<Edge>()); //각 도시의 버스노선 리스트초기화
		}
		for(int m=0;m<M;m++) {
			StringTokenizer st = new StringTokenizer(br.readLine());
			int start = Integer.parseInt(st.nextToken());
			int end = Integer.parseInt(st.nextToken());
			int weight = Integer.parseInt(st.nextToken());
			vertex.get(start).add(new Edge(end,weight)); //각 도시의 버스노선 add
		}
		StringTokenizer st = new StringTokenizer(br.readLine());
		int start = Integer.parseInt(st.nextToken());
		int end = Integer.parseInt(st.nextToken());
		minDist = new int[N+1];
		Arrays.fill(minDist, 987654321); // 다익스트라 초기값 INF
		track = new int[N+1];
		bfs(start); //bfs
		ArrayDeque <Integer>dq = new ArrayDeque<>();
		int now = end;
		while(now!=start) {
			cityCount++;
			dq.addFirst(now);
			now = track[now];
		}
		dq.addFirst(now);
		cityCount++;
		// 시작 - 중간도시1 - 중간도시2 - ... - 도착
		
		StringBuilder sb = new StringBuilder();
		sb.append(minDist[end]).append("\n").append(cityCount).append("\n");
		while(!dq.isEmpty()) {
			sb.append(dq.pollFirst()).append(" ");
		}
		System.out.println(sb);
	}
	static void bfs(int start) {
		PriorityQueue<Edge> pq = new PriorityQueue<>();
		minDist[start] = 0;
		pq.add(new Edge(start, 0));
		while(!pq.isEmpty()) {
			Edge now = pq.poll();
			
			if(visit[now.end]) continue; // 이미방문
			
			visit[now.end]=true; //방문처리
			for(Edge edge : vertex.get(now.end)) { //도시내의 버스리스트
				if(minDist[edge.end] > minDist[now.end] + edge.weight) { //현재도시까지 최소비용 > 이전도시까지 비용 + 버스비용  
					minDist[edge.end] = minDist[now.end] + edge.weight; //갱신
					pq.add(new Edge(edge.end,minDist[edge.end])); //다음경로 현재도시
					track[edge.end] = now.end; //도시 경로저장용
				}
			}
		}
	}
}

1. vertex, edge처리 (도시가 1000이면 인접행렬써도 될 것 같지만 그래도 인접 리스트를 썼다)
2. bfs 이므로 당연히 큐(다익스트라니까 우선순위 큐)
3. weight 계산하면서 최소 갱신하면서 경로 만들기

어려웠던 점은. 최소 경로를 나타내는 것이었는데 도시전체 리스트를 만들자니 안지나가는 도시들도 있고 해서 배열로 만든다음 덱사용해서 앞에 넣고 순서대로 뽑아주었다.

샘플 결과와 다르게 나오는데 통과가 되는 신기한 마술쇼.