[백준 10853] Change of Scenery - JAVA

문제 링크

문제 정의

기존 최단 거리와 동일한 거리로 다른 경로가 존재하는지 판단

조건

• 시간(거리)은 절대 늘어나면 안 됨
• 적어도 한 개의 간선은 기존 경로와 달라야 함

입력

• 입력 조건 정리
• 정점 개수: $(N ≤ 10,000)$
• 간선 개수: $(M ≤ 1,000,000)$
• 기존 경로 길이: $(K ≤ N ≤ 10,000)$

주어지는 것:

• $1 → N$까지의 최단 경로 (route)
• 전체 그래프 (무방향, 가중치 존재)

접근 방법

기존 다익스트라와 동일하게 수행하며
$1 → N$까지 최단 경로는 dist[N]에 저장되어 있습니다.

그러나 이 최단 경로를 다른 경로로 탐색한 경우가 있는지 확인하기 위해서는
vis 배열을 추가해서 현재 측정된 최단 경로로 몇 개의 경로가 올 수 있는지를 저장해
새로운 경로로 이동할 때 현재 최단 경로와 같은지(dist[nv] == nw) 파악하고
기존 경로vis[nv] += vis[v]를 누적하는 로직을 추가했습니다.

코드

import java.io.*;
import java.util.*;

class Edge implements Comparable<Edge> {
	int v;
	int w;

	public Edge(int v, int w) {
		this.v = v;
		this.w = w;
	}

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

public class Main {
	static final int MAX = 2000000000;

	static StringTokenizer st;
	static ArrayList<Edge>[] graph;

	static int[] dist;
	static int[] vis;
	static int N, M, K;

	public static void main(String[] args) throws IOException {
		init();
		System.out.println(dijkstra());
	}

	static void init() throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		st = new StringTokenizer(br.readLine());

		N = Integer.parseInt(st.nextToken());
		M = Integer.parseInt(st.nextToken());
		K = Integer.parseInt(st.nextToken());

		st = new StringTokenizer(br.readLine());
		for (int i = 0; i < K; i++) st.nextToken();

		graph = new ArrayList[N + 1];
		for (int i = 1; i <= N; i++) graph[i] = new ArrayList<>();

		for (int i = 0; i < M; i++) {
			st = new StringTokenizer(br.readLine());
			int u = Integer.parseInt(st.nextToken());
			int v = Integer.parseInt(st.nextToken());
			int w = Integer.parseInt(st.nextToken());

			graph[u].add(new Edge(v, w));
			graph[v].add(new Edge(u, w));
		}

		dist = new int[N + 1];
		vis = new int[N + 1];
		Arrays.fill(dist, MAX);
	}

	static String dijkstra() {
		PriorityQueue<int[]> pq = new PriorityQueue<>(Comparator.comparingInt(a -> a[1]));

		dist[1] = 0;
		vis[1] = 1;
		pq.offer(new int[]{1, 0});

		while (!pq.isEmpty()) {
			int[] cur = pq.poll();
			int v = cur[0];
			int d = cur[1];

			if (dist[v] < d) continue;

			for (Edge next : graph[v]) {
				int nv = next.v;
				int nd = d + next.w;

				if (dist[nv] > nd) {
					dist[nv] = nd;
					vis[nv] = vis[v];
					pq.offer(new int[]{nv, nd});
				}
				else if (dist[nv] == nd) {
					vis[nv] = Math.min(2, vis[nv] + vis[v]);
				}
			}
		}

		return vis[N] >= 2 ? "yes" : "no";
	}
}