백준 거의 최단 경로(5719)

거의 최단 경로

1. 힌트

1) 다익스트라를 통해서 정점 $S$에서 모든 정점으로의 최단 거리를 구할 수 있습니다. 어떤 간선이 최단 경로에 속하는지 판단할 때, $S$에서 $D$로 가면서 판단하기는 어렵지만 거꾸로 가면서 판단하기는 쉽습니다.

2) 다익스트라를 통해 시작점 $S$에서의 최단 거리를 담은 배열 $dist$를 얻을 수 있습니다. 이 때, 도착점 D에서 최단경로에 속하는 간선만 타고 거꾸로 올라간다고 가정해보겠습니다. 만약 간선 $(x,\ D)$가 존재하고, $dist[x] + w(x,\ D) = dist[D]$

3) $D$에서 $S$로 이동하면서 최단 경로에 속하는 간선을 삭제할 때, 똑같은 정점을 두 번 이상 방문하는 것을 막기 위해 DFS혹은 BFS를 사용해줍니다.

2. 접근

1) 뒤에서부터 생각해서 문제를 풀 수 있을까?

도착점 $D$에서 $S$로 반대로 이동하면서 최단경로에 속하는 간선을 찾습니다. 그 과정에서 $dist[u] + w(u,\ v) = dist[v]$

3. 구현

역방향 간선을 쉽게 찾게 하기 위해서 인접 행렬 방식으로 그래프를 구현해야 하나 고민했는데, 그렇게 하면 다익스트라의 시간 복잡도가 증가하기 때문에 역방향 간선을 저장하는 그래프를 따로 구현했습니다 그것이 adj2입니다.

간선을 삭제하는 것은 인접 행렬 방식으로 $boolean$배열을 사용했습니다. 이렇게 하면 다익스트라 코드를 재활용 할 수 있습니다.

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

public class Main {
	static int N;
	// 인접 리스트 방식으로 간선을 저장
	static ArrayList<ArrayList<Pair>> adj;
	// 기존의 간선들을 거꾸로 저장해 놓은 간선
	static ArrayList<ArrayList<Pair>> adj2;
	// 어떤 간선이 삭제되었는지 여부를 저장
	static boolean[][] removed;
	
	static final int INF = 987654321;
	
	// start정점에서 모든 정점으로의 최단거리를 저장한 dist[] 반환
	static int[] dijkstra(int start) {
		PriorityQueue<Pair> pq = new PriorityQueue<>();
		pq.offer(new Pair(start, 0));
		int[] dist = new int[N];
		Arrays.fill(dist, INF);
		dist[start] = 0;
		while (!pq.isEmpty()) {
			Pair p = pq.poll();
			int here = p.num; int cost = p.cost;
			if (dist[here] < cost) continue;
			// 인접한 정점 중 삭제되지 않은 간선만 검사한다
			for (Pair edge : adj.get(here)) if (!removed[here][edge.num]) {
				int there = edge.num;
				int nextCost = cost + edge.cost;
				if (dist[there] > nextCost) {
					dist[there] = nextCost;
					pq.offer(new Pair(there, nextCost));
				}
			}
		}
		return dist;
	}
	
	// start에서 역방향 간선을 찾아가면서 최단경로에 속하는 간선을 지운다
	// 같은 정점을 여러번 방문하는 것을 막기 위해 BFS사용
	static void bfs(int[] dist, int start) {
		Queue<Integer> q = new LinkedList<>();
		q.offer(start);
		boolean[] booked = new boolean[N];
		booked[start] = true;
		while (!q.isEmpty()) {
			int here = q.poll();
			for (Pair edge : adj2.get(here)) {
				int there = edge.num; int weight = edge.cost;
				// 조건을 만족하면 there정점에서 here로 오는 경로는 최단경로에 속한다
				// there이 이미 방문한 정점이더라도 edge(here, there)을 검사한다
				if (dist[there] + weight == dist[here]) {
					if (!booked[there]) {
						q.offer(there);
						booked[there] = true;
					}
					// 현재 역방향 간선을 탐색중이므로 edge(there, here)이 제거됨
					removed[there][here] = true;
				}
			}
		}
		
	}
	
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringBuilder bw = new StringBuilder();
		while (true) {
			StringTokenizer st = new StringTokenizer(br.readLine(), " ");
			N = Integer.parseInt(st.nextToken());
			int M = Integer.parseInt(st.nextToken());
			if (N == 0 && M == 0) break;
			st = new StringTokenizer(br.readLine(), " ");
			int S = Integer.parseInt(st.nextToken());
			int D = Integer.parseInt(st.nextToken());
			adj = new ArrayList<>(N); adj2 = new ArrayList<>(N);
			for (int i = 0; i < N; i++) {
				adj.add(new ArrayList<>());
				adj2.add(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 p = Integer.parseInt(st.nextToken());
				adj.get(u).add(new Pair(v, p));
				// 역추적할 때 사용할 수 있도록 반대로도 넣어 놓는다
				adj2.get(v).add(new Pair(u, p));
			}
			removed = new boolean[N][N];
			bfs(dijkstra(S), D);
			int ret = dijkstra(S)[D];
			bw.append(ret == INF ? -1 : ret).append("\n");
		}
		System.out.print(bw);
	}
	
}

class Pair implements Comparable<Pair> {
	int num, cost;

	Pair(int t, int w) { num = t; cost = w; }
	
	@Override
	public int compareTo(Pair o) { return cost - o.cost; }
	
}

1) 시간 복잡도

2) 테스트 케이스

6 8
0 5
0 1 1
1 2 1
2 3 1
3 4 1
4 5 1
0 2 2
2 5 10
0 5 5
->-1

이와 같이 생긴 그래프입니다. 빨간색 선으로 표시한건 최단 경로들입니다. 최단 경로의 길이는 $5$임을 쉽게 알 수 있죠. 그리고 최단 경로를 모두 삭제하면 $0$번 간선에서 나올 방법이 없으니 $-1$을 반환해야 합니다. 그런데 역추적하면서 간선을 삭제하는 BFS를 잘못짜면 거의 최단 경로의 길이도 $5$라는 이상한 결과가 나옵니다.

// 조건을 만족하면 there정점에서 here로 오는 경로는 최단경로에 속한다
if (dist[there] + weight == dist[here] && !booked[there]) {
	q.offer(there);
	booked[there] = true;
	// 현재 역방향 간선을 탐색중이므로 edge(there, here)이 제거됨
	removed[there][here] = true;
}

제가 잘못 짰던 코드의 예시입니다. 조건문의 !booked[there]에 유의하세요. 일반적으로 BFS에서 인접한 정점들을 검사할 때, 이미 방문하지 않은 정점만(혹은 방문이 예약되어있지 않은) 확인하는데요, 이 문제에서는 인접한 정점이 이미 확인된 정점이어도 우리는 최단 경로에 속하는 간선을 확인해야 하기 때문에 간선은 모두 확인해주어야 합니다.

// 조건을 만족하면 there정점에서 here로 오는 경로는 최단경로에 속한다
// there이 이미 방문한 정점이더라도 edge(here, there)을 검사한다
if (dist[there] + weight == dist[here]) {
	if (!booked[there]) {
		q.offer(there);
		booked[there] = true;
	}
	// 현재 역방향 간선을 탐색중이므로 edge(there, here)이 제거됨
	removed[there][here] = true;
}

이와 같이 바꿔줘야하겠죠.