[BOJ] 9370: 미확인 도착지 (JAVA)

문제

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

 

 

풀이

이 문제는 출발지에서 도착지까지의 최단경로를 구했을 때, 그 최단경로에 g와 h 교차로 사이에 있는 도로를 지나가는지 확인하면 되는 문제이다. 

 

따라서 다익스트라 알고리즘을 사용해서 풀이할 수 있다. 

 

문제를 풀 때 고려해야 할 점은 최단경로가 여러 개일 때, 어떻게 g와 h 교차로 사이에 있는 도로를 지나가도록 할 수 있느냐이다. 이 부분에서 막혀서 풀이를 참고했는데 방법은 아주 간단했다.

 

 

방법 1

g와 h 교차로 사이에 있는 도로를 지나가기 위해서는 그 도로에 우선순위를 줘야 한다. 따라서 모든 도로 길이에 2를 곱해서 저장한 뒤, g와 h 교차로 사이에 있는 도로 길이에 1을 빼서 우선순위를 주면 된다. 

 

즉, 아래 그림과 같이 최단경로가 여러 개 있을 때 g와 h 교차로 사이에 있는 도로를 선택하도록 하는 것이다. 

 

방법 2

위의 방법은 사실 생각하기 어려울 수 있다. (그게 바로 나)

 

가장 단순하게 푸는 방법은 start > g > h > end, start > h > g > end의 경로로 탐색했을 때의 최단거리가 start > end 경로로 탐색했을 때의 최단거리와 같은지 비교하면 된다. 

 

즉, 다익스트라 알고리즘을 여러 번 호출해서 구하면 된다.

 

방법 1 vs 방법 2

두 방법의 시간 차이를 비교하면 확실히 다익스트라 알고리즘을 2번만 호출하는 방법 1이 시간과 메모리를 덜 잡아먹는 것을 알 수 있다. 

아래: 방법 1, 위: 방법 2

 

1번 방법이 시간과 메모리를 덜 잡아먹지만, 개인적으로 1번을 떠올리기 어려울 것 같아서 이렇게 풀 수 있구나-- 정도로만 기억하고 2번을 중점으로 익힐까 싶다.

 

코드

방법 1

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

public class BOJ_9370 {

	static int INF = 1_000_000_000;
	static int[] minDist;
	static boolean[] visited;
	static ArrayList<Node>[] graph;

	public static void main(String[] args) throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		// 목적지까지 최단거리로 갈 것
		int T = Integer.parseInt(br.readLine());
		StringTokenizer st = null;
		StringBuilder sb = new StringBuilder();
		for (int tc = 0; tc < T; tc++) {
			st = new StringTokenizer(br.readLine());
			int n = Integer.parseInt(st.nextToken()); // 교차로의 개수
			int m = Integer.parseInt(st.nextToken()); // 도로의 개수
			int t = Integer.parseInt(st.nextToken()); // 목적지 후보의 개수

			st = new StringTokenizer(br.readLine());
			int s = Integer.parseInt(st.nextToken()); // 예술가들의 출발지
			int g = Integer.parseInt(st.nextToken());
			int h = Integer.parseInt(st.nextToken());

			minDist = new int[n + 1];
			visited = new boolean[n + 1];

			graph = new ArrayList[n + 1];
			for (int i = 1; i <= n; i++) {
				graph[i] = new ArrayList<Node>();
			}

			for (int i = 0; i < m; i++) {
				st = new StringTokenizer(br.readLine());
				int a = Integer.parseInt(st.nextToken());
				int b = Integer.parseInt(st.nextToken());
				// 동일한 최단거리가 있을 때, g - h 사이 간선에 우선순위를 주기
				int d = Integer.parseInt(st.nextToken()) * 2; // 모든 가중치에 * 2
				if ((a == g && b == h) || (a == h && b == g)) {
					// g - h 사이 간선이라면 -1을 해서 우선순위 주기
					d--;
				}
				graph[a].add(new Node(b, d));
				graph[b].add(new Node(a, d));
			}

			ArrayList<Integer> answer = new ArrayList<>();
			for (int i = 0; i < t; i++) {
				Arrays.fill(minDist, INF);
				Arrays.fill(visited, false);

				int end = Integer.parseInt(br.readLine());
				int dist = dijkstra(s, end);
				if (dist == -1) // 목적지까지 이동이 불가능하다면 continue
					continue;

				// 최단거리가 홀수면 g - h 사이 간선을 지나갔다는 뜻
				if (dist % 2 == 1) {
					answer.add(end);
				}
			}

			Collections.sort(answer); // 오름차순 정렬
			for (int a : answer) {
				sb.append(a).append(" ");
			}
			sb.append("\n");
		}
		System.out.println(sb);
	}

	static int dijkstra(int start, int end) {
		PriorityQueue<Node> pq = new PriorityQueue<>((n1, n2) -> Integer.compare(n1.d, n2.d));
		pq.offer(new Node(start, 0));
		minDist[start] = 0;

		while (!pq.isEmpty()) {
			Node now = pq.poll();
			if (now.x == end)
				return now.d;

			if (visited[now.x])
				continue;
			visited[now.x] = true;

			for (Node next : graph[now.x]) {
				if (!visited[next.x] && minDist[next.x] > minDist[now.x] + next.d) {
					minDist[next.x] = minDist[now.x] + next.d;
					pq.offer(new Node(next.x, minDist[next.x]));
				}
			}
		}
		return -1;
	}

	static class Node {
		int x, d;

		public Node(int x, int d) {
			this.x = x;
			this.d = d;
		}
	}
}

 

방법 2

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

public class BOJ_9370 {

	static int INF = 10_000_000;
	static int[] minDist;
	static boolean[] visited;
	static ArrayList<Node>[] graph;

	public static void main(String[] args) throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		// 목적지까지 최단거리로 갈 것
		int T = Integer.parseInt(br.readLine());
		StringTokenizer st = null;
		StringBuilder sb = new StringBuilder();
		for (int tc = 0; tc < T; tc++) {
			st = new StringTokenizer(br.readLine());
			int n = Integer.parseInt(st.nextToken()); // 교차로의 개수
			int m = Integer.parseInt(st.nextToken()); // 도로의 개수
			int t = Integer.parseInt(st.nextToken()); // 목적지 후보의 개수

			st = new StringTokenizer(br.readLine());
			int s = Integer.parseInt(st.nextToken()); // 예술가들의 출발지
			int g = Integer.parseInt(st.nextToken());
			int h = Integer.parseInt(st.nextToken());

			minDist = new int[n + 1];
			visited = new boolean[n + 1];

			graph = new ArrayList[n + 1];
			for (int i = 1; i <= n; i++) {
				graph[i] = new ArrayList<Node>();
			}

			for (int i = 0; i < m; i++) {
				st = new StringTokenizer(br.readLine());
				int a = Integer.parseInt(st.nextToken());
				int b = Integer.parseInt(st.nextToken());
				int d = Integer.parseInt(st.nextToken());
				graph[a].add(new Node(b, d));
				graph[b].add(new Node(a, d));
			}

			ArrayList<Integer> answer = new ArrayList<>();
			for (int i = 0; i < t; i++) {
				int end = Integer.parseInt(br.readLine());

				// s > g > h > end
				int d1 = dijkstra(s, g) + dijkstra(g, h) + dijkstra(h, end);

				// s > h > g > end
				int d2 = dijkstra(s, h) + dijkstra(h, g) + dijkstra(g, end);

				// s > end
				int d3 = dijkstra(s, end);

				// 두 방법 중 하나라도 최단경로를 찾으면 기록하기
				if (Math.min(d1, d2) == d3) {
					answer.add(end);
				}
			}

			Collections.sort(answer); // 오름차순 정렬
			for (int a : answer) {
				sb.append(a).append(" ");
			}
			sb.append("\n");
		}
		System.out.println(sb);
	}

	static int dijkstra(int start, int end) {
		Arrays.fill(minDist, INF);
		Arrays.fill(visited, false);

		PriorityQueue<Node> pq = new PriorityQueue<>((n1, n2) -> Integer.compare(n1.d, n2.d));
		pq.offer(new Node(start, 0));
		minDist[start] = 0;

		while (!pq.isEmpty()) {
			Node now = pq.poll();
			if (now.x == end)
				return now.d;

			if (visited[now.x])
				continue;
			visited[now.x] = true;

			for (Node next : graph[now.x]) {
				if (!visited[next.x] && minDist[next.x] > minDist[now.x] + next.d) {
					minDist[next.x] = minDist[now.x] + next.d;
					pq.offer(new Node(next.x, minDist[next.x]));
				}
			}
		}
		return INF;
	}

	static class Node {
		int x, d;

		public Node(int x, int d) {
			this.x = x;
			this.d = d;
		}
	}
}

 

후기

처음에는 문제를 제대로 이해하지 못해서 질문 게시판을 통해 이해했다...ㅎ 그리고 아이디어가 필요한 1번 방법이 아니더라도 2번 방법처럼 풀어서 생각할 수 있어야 했는데 그러지 못했다. 그냥 빨리 푸는 것에만 급급해서 여러 반례들을 생각하지 않았던 것 같다. 제발 문제를 풀고 넘기는 것에만 집착하지 말고 반례까지 잘 생각해보도록 노력하자!

---

참고

https://dragon-h.tistory.com/22