[Java] 백준 / 무엇을 아느냐가 아니라 누구를 아느냐가 문제다 / 9694

[Java] 백준 / 무엇을 아느냐가 아니라 누구를 아느냐가 문제다 / 9694

문제

문제 링크

접근 방식

1. 다익스트라 알고리즘을 사용하되 최고의원을 최소 친밀도로 만날때까지 거쳤던 모든 정점을 출력하는 방법만 따로 구현하면 된다
2. 및의 알고리즘에서는 시작점에서 각각의 끝 점중 가장 짧은 거리를 저장하는 distance 배열 뒤에 추가로 연결했을 때의 바로 전 점을 저장한다
3. 최고의원을 만났을 때 해당 점 바로 전 점을 계속 탐색하여 스택에 넣었다
4. 마지막으로 스택에 값이 있다면 최고의원을 만난 것이기 때문에 스택에서 하나씩 빼서 출력하고, 값이 없다면 -1을 출력한다

코드

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

public class Main_9694 {

	
	public static class Vertex implements Comparable<Vertex>{
		int no;
		int w;
		
		Vertex(int no, int w){
			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));
		StringBuilder sb = new StringBuilder();
		int T = Integer.parseInt(br.readLine());
		
		for(int tc=1;tc<=T;tc++) {
			StringTokenizer st = new StringTokenizer(br.readLine());
			int N = Integer.parseInt(st.nextToken());
			int M = Integer.parseInt(st.nextToken());
			
			ArrayList<ArrayList<Vertex>> list = new ArrayList<>();
			for(int i=0;i<M;i++) {
				list.add(new ArrayList<>());
			}
			
			for(int i=0;i<N;i++) {
				st = new StringTokenizer(br.readLine());
				int x = Integer.parseInt(st.nextToken());
				int y = Integer.parseInt(st.nextToken());
				int z = Integer.parseInt(st.nextToken());
				
				list.get(x).add(new Vertex(y,z));
				list.get(y).add(new Vertex(x,z));
			}
			
			int[][] distance = new int[M][2];
			boolean[] visited = new boolean[M];
			
			for(int i=0;i<M;i++) {
				distance[i] = new int[] {Integer.MAX_VALUE, -1};
			}
			
			int start = 0;
			distance[start][0] = 0;
			
			PriorityQueue<Vertex> pq = new PriorityQueue<>();
			pq.offer(new Vertex(start,distance[start][0]));
			
			Stack<Integer> answer = new Stack<>();
			
			while(!pq.isEmpty()) {
				int current = pq.poll().no;
				
				if(visited[current]) continue;
				visited[current] = true;
				
				if(current == M-1) {
					while(current != -1) {
						answer.push(current);
						current = distance[current][1];
					}
					break;
				}
				
				for(Vertex v : list.get(current)) {
					if(distance[v.no][0] > distance[current][0] + v.w) {
						distance[v.no][0] = distance[current][0] + v.w;
						distance[v.no][1] = current;
						pq.offer(new Vertex(v.no,distance[v.no][0]));
					}
				}
			}
			
			
			sb.append("Case #"+tc+": ");
			if(answer.size() > 0) {
				while(!answer.isEmpty()) sb.append(answer.pop() + " ");
				
				sb.setLength(sb.length()-1);
				
			}
			
			else {
				sb.append(-1);
			}
			sb.append("\n");
			
			
		}
		System.out.print(sb);
	}

}