사전순으로 최소인 최단 경로

문제. 모든 간선의 가중치가 1인 (유향) 그래프 $G = (V, E)$와 시작점 $s$, 끝점 $t$가 주어졌다고 하자. 각 간선 $e \in E$에는 label $\ell(e)$가 있다. $s$에서 $t$로 간선 $e_1, e_2, \cdots, e_k$를 거쳐 이동하는 경로를 경로 튜플 $(\ell(e_1), \ell(e_2), \cdots, \ell(e_k))$로 표현하자. $s$에서 $t$로의 모든 최단 경로 가운데 경로 튜플 이 사전순으로 최소인 경로를 찾아보자.

 

 

일단, $s$에서 BFS를 돌리며, $O(|V| + |E|)$ 시간에 shortest path spanning tree를 만들 수 있다. 고로, $d(u) + 1 = d(v)$를 만족하는 $u \to v$ 간선만 남겨두고 생각할 수 있다.

 

이후, $t$에서 시작해 역방향 BFS를 돌리며, $O(|V| + |E|)$ 시간에 shortest path spanning tree의 간선들 가운데 $d(u, t) = d(v, t) + 1$을 만족하는 간선만을 남겨둘 수 있다.

 

마지막으로, $s$에서 시작해, 매 정점에서 여전히 남아 있는 '나가는' 간선 가운데 label이 최소인 것만을 택해서 이동하면, 원하는 경로를 얻게 된다.

 

이를 이용하면, BOJ 18121 문자열 압축 문제를 해결할 수 있다.

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