링크
https://www.acmicpc.net/problem/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개로 향하는 최단 경로의 일부이다.
출력
테스트 케이스마다
- 입력에서 주어진 목적지 후보들 중 불가능한 경우들을 제외한 목적지들을 공백으로 분리시킨 오름차순의 정수들로 출력한다.
풀이
import java.util.*;
public class boj_9370 {
public static final int INF = (int) 1e9; // 무한을 의미하는 값으로 10억을 설정
public static int T, n, m, t, s, g, h;
// 각 노드에 연결되어 있는 노드에 대한 정보를 담는 배열
public static ArrayList<ArrayList<Node>> graph;
// 최단 거리 테이블 만들기
public static int[] d;
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
T = sc.nextInt();
for (int j = 0; j < T; j++){
n = sc.nextInt();
m = sc.nextInt();
t = sc.nextInt();
graph = new ArrayList<>();
s = sc.nextInt();
g = sc.nextInt();
h = sc.nextInt();
// 그래프 초기화
for (int i = 0; i <= n; i++) {
graph.add(new ArrayList<>());
}
// 모든 간선 정보를 입력받기
for (int i = 0; i < m; i++) {
int a = sc.nextInt();
int b = sc.nextInt();
int d = sc.nextInt();
// a번 노드에서 b번 노드로 가는 비용이 c라는 의미
graph.get(a).add(new Node(b, d));
graph.get(b).add(new Node(a, d));
}
PriorityQueue<Integer> pq = new PriorityQueue<>();
int[] des = new int[t];
for (int i = 0; i < t; i++){
des[i] = sc.nextInt();
}
for (int d : des) {
long res1 = dijkstra(s, g) + dijkstra(g, h) + dijkstra(h, d);
long res2 = dijkstra(s, h) + dijkstra(h, g) + dijkstra(g, d);
long res3 = dijkstra(s, d);
if (Math.min(res1, res2) == res3) {
pq.add(d);
}
; }
while (!pq.isEmpty()) {
System.out.print(pq.poll() + " ");
}
System.out.println();
}
}
public static int dijkstra(int start, int end) {
d = new int[n + 1];
Arrays.fill(d, INF);
PriorityQueue<Node> pq = new PriorityQueue<>();
// 시작 노드로 가기 위한 최단 경로는 0으로 설정하여, 큐에 삽입
pq.add(new Node(start, 0));
d[start] = 0;
while(!pq.isEmpty()) { // 큐가 비어있지 않다면
// 가장 최단 거리가 짧은 노드에 대한 정보 꺼내기
Node node = pq.poll();
int now = node.index; // 현재 노드
int dist = node.distance; // 현재 노드까지의 비용
// 현재 노드가 이미 처리된 적이 있는 노드라면 무시
if (d[now] < dist) continue;
// 현재 노드와 연결된 다른 인접한 노드들을 확인
for (int i = 0; i < graph.get(now).size(); i++) {
int cost = d[now] + graph.get(now).get(i).distance;
// 현재 노드를 거쳐서, 다른 노드로 이동하는 거리가 더 짧은 경우
if (cost < d[graph.get(now).get(i).index]) {
d[graph.get(now).get(i).index] = cost;
pq.offer(new Node(graph.get(now).get(i).index, cost));
}
}
}
return d[end];
}
}설명
다익스트라 알고리즘 자체는 같지만 거기서 계속 응용하고 변형하는걸 알아채는 과정이 어렵다...! 참고 블로그에 설명이 잘 나와 있어서 이해할 수 있었다.
