[백준] 9370 - 미확인 도착지 (자바 Java)

[Gold II] 미확인 도착지 - 9370

문제 링크

성능 요약

메모리: 283148 KB, 시간: 1220 ms

분류

다익스트라(dijkstra), 그래프 이론(graphs)

문제 설명

(취익)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개로 향하는 최단 경로의 일부이다.

출력

테스트 케이스마다

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

---

다익스트라를 사용하면 된다고 생각했는데, 시행착오를 많이 겪었다.

 

처음에는 각각의 후보에 대해 다익스트라를 돌리면 된다고 생각했다.

1. 다익스트라를 돌리면서 g와 h가 연결된 도로를 방문할 경우 결과에 추가하도록 했는데, 생각해보니 pq에서 poll하여 그 도로를 방문한다고 무조건 최단 경로에 포함되는 것이 아니었다.

 

2. 그래서 각각의 다익스트라에서 도착후보지까지 도착하는 경로를 저장하고, 그 경로를 거꾸로 훑으며 g와 h사이의 도로가 포함되었을 경우 true를 리턴하도록 했다.

이렇게 하면 모든 경우의 수에 대해 다익스트라를 여러번 돌려 시간 초과가 발생했다.

 

3. 그러면 다익스트라를 한 번만 돌리고, 그 route를 저장해야 하나? 생각했는데 route를 거슬러 올라가는 과정에서 여전히 시간초과가 발생했다.

 

최종 풀이. 결국 g-h가 지나는 도로가 최단 경로에 포함되려면

st - ed까지의 최단 거리 = (st-g) + (g-h) + (h-ed) 각각의 최단거리

여야 한다.

문제 조건은 무향 그래프이기 때문에

(st-h) + (h-g) + (g-ed)의 경우도 확인해야 한다.

이 거리들을 구하려면

1. st에서 다익스트라

2. g에서 다익스트라

3. h에서 다익스트라

총 3번의 다익스트라를 실행한 후, 도착 후보지에 따라 각각의 거리들의 합이 최단거리의 합과 동일한지를 확인하면 된다.

 

---

전체 코드

package BOJ.Gold.g2;

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

public class BOJ_9370_미확인도착지 {

	static class Edge implements Comparable<Edge> {
		int st;
		int ed;
		int dist;

		public Edge(int st, int ed, int dist) {
			this.st = st;
			this.ed = ed;
			this.dist = dist;
		}

		@Override
		public int compareTo(Edge o) {
			return this.dist - o.dist;
		}

	}

	static int n, m, t;
	static int s, g, h;
	static List<Edge>[] adjList;
	static int[] edArr;
	static int[][] dist;
	static StringBuilder sb = new StringBuilder();

	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int tc = sc.nextInt();
		while (tc-- > 0) {
			n = sc.nextInt(); // vertex
			m = sc.nextInt(); // edge
			t = sc.nextInt(); // 목적지 후보
			s = sc.nextInt(); // 시작점
			g = sc.nextInt(); // 반드시 거쳐야하는 교차로
			h = sc.nextInt();
			adjList = new ArrayList[n + 1];
			for (int i = 1; i <= n; i++)
				adjList[i] = new ArrayList<>();
			int edge = 0;
			// edge adjList
			while (m-- > 0) {
				int a = sc.nextInt();
				int b = sc.nextInt();
				int d = sc.nextInt();
				adjList[a].add(new Edge(a, b, d));
				adjList[b].add(new Edge(b, a, d));
				if ((a == g && b == h) || a == h && b == g)
					edge = d;
			}

			edArr = new int[t];
			for (int i = 0; i < t; i++)
				edArr[i] = sc.nextInt();
			Arrays.sort(edArr); // 후보지는 오름차순으로 출력

//			for (int i = 0; i < t; i++) {
//				if (dijkstra(s, edArr[i]))
//					check = true; // 각각의 후보지에 대해 dijkstra -> 이러면 시간 초과 그냥 dijkstra를 끝까지 돌린 다음 후보지를 확인해야함
//			}

			dist = new int[3][n + 1]; // 0은 s, 1은 g에서 시작, 2는 h에서 시작
			dijkstra(s, 0);
			dijkstra(g, 1);
			dijkstra(h, 2);
			// s->ed = s-g-h-ed 라면 ok 무향이니까 s-h-g-ed도 ok
			boolean check = false;
			for (int i = 0; i < t; i++) {
				int ed = edArr[i];
				if ((dist[0][ed] == dist[0][g] + edge + dist[2][ed])
						|| dist[0][ed] == dist[0][h] + edge + dist[1][ed]) {
					sb.append(ed + " ");
					check = true;
				}
			}
			if (check)
				sb.append("\n");

		}
		System.out.println(sb);
	}

	static void dijkstra(int st, int idx) {

		PriorityQueue<Edge> pq = new PriorityQueue<>();
		boolean[] visited = new boolean[n + 1];

		Arrays.fill(dist[idx], Integer.MAX_VALUE);
		dist[idx][st] = 0;
		// start에서 연결된 edge들을 pq에 추가
		for (int i = 0; i < adjList[st].size(); i++) {
			Edge e = adjList[st].get(i);
			dist[idx][e.ed] = e.dist;
			pq.add(e);
		}
		visited[st] = true;

		while (!pq.isEmpty()) {
			Edge e = pq.poll();
			if (visited[e.ed])
				continue;

//			if ((e.st == g && e.ed == h) || (e.st == h && e.ed == g)) {
//				sb.append(ed).append(" ");
//				return;
//			} // 이렇게하면 목적지까지 최단 경로가 아님에도 포함한다고 인식함

			visited[e.ed] = true;
			for (Edge tmp : adjList[e.ed]) {
				if (!visited[tmp.ed] && dist[idx][tmp.ed] > dist[idx][tmp.st] + tmp.dist) {
					dist[idx][tmp.ed] = dist[idx][tmp.st] + tmp.dist;
					pq.add(new Edge(tmp.st, tmp.ed, dist[idx][tmp.ed]));
				}
			}

		}

	}

}