백준 | 9370번. 미확인 도착지 - 다익스트라

⬛ 백준 9370번. 미확인 도착지 - 다익스트라

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

9370번: 미확인 도착지

문제

(취익)B100 요원, 요란한 옷차림을 한 서커스 예술가 한 쌍이 한 도시의 거리들을 이동하고 있다. 너의 임무는 그들이 어디로 가고 있는지 알아내는 것이다. 우리가 알아낸 것은 그들이 s지점에서 출발했다는 것, 그리고 목적지 후보들 중 하나가 그들의 목적지라는 것이다. 그들이 급한 상황이기 때문에 목적지까지 우회하지 않고 최단거리로 갈 것이라 확신한다. 이상이다. (취익)

어휴! (요란한 옷차림을 했을지도 모를) 듀오가 어디에도 보이지 않는다. 다행히도 당신은 후각이 개만큼 뛰어나다. 이 후각으로 그들이 g와 h 교차로 사이에 있는 도로를 지나갔다는 것을 알아냈다.

이 듀오는 대체 어디로 가고 있는 것일까?

문제 설명 그림

예제 입력의 두 번째 케이스를 시각화한 것이다. 이 듀오는 회색 원에서 두 검은 원 중 하나로 가고 있고 점선으로 표시된 도로에서 냄새를 맡았다. 따라서 그들은 6으로 향하고 있다.

입력

첫 번째 줄에는 테스트 케이스의 T(1 ≤ T ≤ 100)가 주어진다. 각 테스트 케이스마다

• 첫 번째 줄에 3개의 정수 n, m, t (2 ≤ n ≤ 2 000, 1 ≤ m ≤ 50 000 and 1 ≤ t ≤ 100)가 주어진다. 각각 교차로, 도로, 목적지 후보의 개수이다.
• 두 번째 줄에 3개의 정수 s, g, h (1 ≤ s, g, h ≤ n)가 주어진다. s는 예술가들의 출발지이고, g, h는 문제 설명에 나와 있다. (g ≠ h)
• 그 다음 m개의 각 줄마다 3개의 정수 a, b, d (1 ≤ a < b ≤ n and 1 ≤ d ≤ 1 000)가 주어진다. a와 b 사이에 길이 d의 양방향 도로가 있다는 뜻이다.
• 그 다음 t개의 각 줄마다 정수 x가 주어지는데, t개의 목적지 후보들을 의미한다. 이 t개의 지점들은 서로 다른 위치이며 모두 s와 같지 않다.

교차로 사이에는 도로가 많아봐야 1개이다. m개의 줄 중에서 g와 h 사이의 도로를 나타낸 것이 존재한다. 또한 이 도로는 목적지 후보들 중 적어도 1개로 향하는 최단 경로의 일부이다.

출력

테스트 케이스마다 입력에서 주어진 목적지 후보들 중 불가능한 경우들을 제외한 목적지들을 공백으로 분리시킨 오름차순의 정수들로 출력한다.

---

💚나의 풀이

• dijkstra(st, ed) 로 정의해서 푼다.
• g와 h를 잇는 도로를 경유해서 최종적으로 t개의 목적지에 도달하느냐는 문제인데

(1) s→g→h→ed 로 거쳐가는 경로

(2) s→h→g→ed 로 거쳐가는 경로

(3) s→ed 직진 경로

• (1)과 (2)의 경로를 비교하여 더 작은 값이 최종적으로 s→ed로 가는 최단 거리와 같다면 pQ에 담도록 처리
• pQ가 자동 정렬 해주므로, 문제에서 원하는 경유지를 거쳐 t의 목적지로 간 경우만 poll하여 출력하면 된다.

package to_0927_6;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.PriorityQueue;
import java.util.Scanner;

/*9370번. 미확인 도착지 */

class Edge implements Comparable<Edge>{
	int e, val;
	Edge(int e, int val){
		this.e = e;
		this.val = val;
	}
	@Override
	public int compareTo(Edge o) {
		// TODO Auto-generated method stub
		return this.val - o.val;
	}
}
public class Main {
	static int T;
	static int n, m, t;//정점, 간선, 목적지 개수 t개
	static int s, g, h;//시작점, 경유지 g-h 
	
	static int[] distance;//거리 배열 
	static ArrayList<ArrayList<Edge>> graph;
	static boolean[] visited;
	static boolean flag;
	
	//다익스트라 
	static int dijkstra(int st, int ed) {
		
		visited = new boolean[n+1];
		PriorityQueue<Edge> pQ = new PriorityQueue<>();
		
		distance=  new int[n+1];
		Arrays.fill(distance, Integer.MAX_VALUE);
		
		distance[st] = 0;
		pQ.offer(new Edge(st, 0));
		
		//목적지에 따라 
		while(!pQ.isEmpty()) {
			Edge cur = pQ.poll();
			//목적지 발견 시 탈출
			if(cur.e == ed) break;//여기서 탈출 
			
			if(visited[cur.e]) continue;
			visited[cur.e] = true;
			
			for(Edge nx : graph.get(cur.e)) {
				if(distance[nx.e] > distance[cur.e] + nx.val) {
					distance[nx.e] = distance[cur.e] + nx.val;
					pQ.offer(new Edge(nx.e, distance[nx.e]));
				}
			}
		}
		
		return distance[ed];
	}
	
	
	//실행 메인 
	public static void main(String[] args) {
		// TODO Auto-generated method stub
		Scanner kb= new Scanner(System.in);
		
		T = kb.nextInt();//테스트 케이스 별
	
		
		for(int a=0; a<T; a++) {
			n = kb.nextInt();
			m = kb.nextInt();
			t = kb.nextInt();//목적지 개수 
			
			s = kb.nextInt();//시작점
			g = kb.nextInt();//경유지 g-h
			h = kb.nextInt();
			
			graph = new ArrayList<>();
			for(int i=0; i<=n; i++) graph.add(new ArrayList<>());
			
			//데이터 입력받기 
			for(int i=0; i<m; i++) {
				int x = kb.nextInt();
				int y = kb.nextInt();
				int val = kb.nextInt();
				//양방향 간선 
				graph.get(x).add(new Edge(y, val));
				graph.get(y).add(new Edge(x, val));
			}
			
			int[] tmp = new int[t];
			for(int i=0; i<t; i++) {
				tmp[i] = kb.nextInt();
			}
			
			//가능한 목적지를 여기에 담아서 자동 정렬 되도록 함 
			PriorityQueue<Integer> pQ = new PriorityQueue<>();
			//각 목적지별로 답을 담을 건데 
			for(int dx : tmp) {
				//1) s->g->h->ed
				int res1  = dijkstra(s, g) + dijkstra(g, h) + dijkstra(h, dx);
				//2) s->h->g -> ed
				int res2 = dijkstra(s, h)+dijkstra(h, g) + dijkstra(g, dx);
				
				//3) s -> ed 다이렉트 
				int res3 = dijkstra(s, dx);
				
				if(Math.min(res1, res2) == res3) {
					pQ.offer(dx);
				}
			}
			//정답 출력
			while(!pQ.isEmpty()) {
				System.out.print(pQ.poll()+" ");
			}
			System.out.println();
		}
	}
}