요즘 많은 자동차에서는 GPS 네비게이션 장비가 설치되어 있다. 네비게이션은 사용자가 입력한 출발점과 도착점 사이의 최단 경로를 검색해 준다. 하지만, 교통 상황을 고려하지 않고 최단 경로를 검색하는 경우에는 극심한 교통 정체를 경험할 수 있다.
상근이는 오직 자기 자신만 사용 가능한 네비게이션을 만들고 있다. 이 네비게이션은 절대로 최단 경로를 찾아주지 않는다. 항상 거의 최단 경로를 찾아준다.
거의 최단 경로란 최단 경로에 포함되지 않는 도로로만 이루어진 경로 중 가장 짧은 것을 말한다.
예를 들어, 도로 지도가 아래와 같을 때를 생각해보자. 원은 장소를 의미하고, 선은 단방향 도로를 나타낸다. 시작점은 S, 도착점은 D로 표시되어 있다. 굵은 선은 최단 경로를 나타낸다. (아래 그림에 최단 경로는 두 개가 있다)거의 최단 경로는 점선으로 표시된 경로이다. 이 경로는 최단 경로에 포함되지 않은 도로로 이루어진 경로 중 가장 짧은 경로이다. 거의 최단 경로는 여러 개 존재할 수도 있다. 예를 들어, 아래 그림의 길이가 3인 도로의 길이가 1이라면, 거의 최단 경로는 두 개가 된다. 또, 거의 최단 경로가 없는 경우도 있다.
입력은 여러 개의 테스트 케이스로 이루어져 있다. 각 테스트 케이스의 첫째 줄에는 장소의 수 N (2 ≤ N ≤ 500)과 도로의 수 M (1 ≤ M ≤ 104)가 주어진다. 장소는 0부터 N-1번까지 번호가 매겨져 있다. 둘째 줄에는 시작점 S와 도착점 D가 주어진다. (S ≠ D; 0 ≤ S, D < N) 다음 M개 줄에는 도로의 정보 U, V, P가 주어진다. (U ≠ V ; 0 ≤ U, V < N; 1 ≤ P ≤ 103) 이 뜻은 U에서 V로 가는 도로의 길이가 P라는 뜻이다. U에서 V로 가는 도로는 최대 한 개이다. 또, U에서 V로 가는 도로와 V에서 U로 가는 도로는 다른 도로이다.
입력의 마지막 줄에는 0이 두 개 주어진다.
출력
각 테스트 케이스에 대해서, 거의 최단 경로의 길이를 출력한다. 만약, 거의 최단 경로가 없는 경우에는 -1을 출력한다.
취업 준비를 위한 알고리즘 풀이 노선으로 갈아타며 방심하고 있던 날 크게 당황시켰던 문제 수많은 맞왜틀과 좌절 끝에 성공시켰지만 2시간이 넘는 오버타임이 걸리고 말았다.
핵심은 '최단 경로를 찾고, 최단 경로에 포함되는 모든 노선을 제거한 후 다시 최단 경로를 찾는 것.' 한 node에서 다른 node까지의 거리를 알고 싶으므로 다익스트라 알고리즘을 사용해 봄직하다. 또한 최단 경로에 해당하는 모든 노선을 제거해야하므로 백트래킹이 필요하다(이 역시 단순한 bfs 혹은 다익스트라로 해결할 수 있다). 그리고 마지막으로 다시 다익스트라 알고리즘을 사용하면 완료. 다익스트라 알고리즘은 우선순위 큐를 사용할 경우 O(ElogV)의 시간복잡도를 가진다.
make_road_dict : 기본 노드 정보를 입력으로 받고, 이를 그래프 형태로 가공하여 반환하는 기본적인 함수.
dijkstra : 다익스트라 알고리즘 함수. 일 대 일 경로 탐색이므로 앞서 말한 대로 다익스트라 알고리즘을 사용할 수 있다. 출발지 노드에서 각 노드까지의 최단거리를 저장한 리스트를 반환한다.
remove_min_route : 최단 경로에 포함되는 경로를 찾는 백트래킹 함수. 본인의 경우 bfs를 사용하였다. 다익스트라 알고리즘에서 반환받은 노드가 쓰이게 된다. 만약 출발지에서 목적지 노드까지 경로상 최단 거리라면, 포함되는 경유지 노드까지의 거리 역시 항상 최단거리이게 된다. 이를 이용해 백트래킹을 구현하고, 최단경로에 해당하는 edge들을 최종적으로 삭제하게 된다.
solve : 위 함수들을 이용하여 문제를 풀이하는 함수.
최단 경로가 하나가 아닐수도, 또 거의 최단 경로 역시 하나가 아닐수도 있으며, 아예 최단 경로가 없을 수도 있다는 점을 명심해야 한다. 또한 백트래킹하겠답시고 다익스트라 과정 중 경로를 일일히 저장하는 실책은 범하지 말도록 하자. (당연히 메모리 초과를 경험하게 된다)
풀이 코드
from collections import defaultdict, deque
from heapq import heappush, heappop
import sys
input = sys.stdin.readline
MAX = float('inf')
def make_road_dict(N, M) :
S, D = map(int, input().split())
road_dict = defaultdict(dict)
rev_road_dict = defaultdict(list)
for _ in range(M) :
U, V, P = map(int, input().split())
road_dict[U][V] = P
rev_road_dict[V].append((U, P))
return S, D, road_dict, rev_road_dict
def dijkstra(S, D, N, road_dict):
dist_lst = [MAX]*N
dist_lst[S] = 0
q = [(0, S)]
while q :
dist, node = heappop(q)
if node == D :
break
if dist_lst[node] < dist :
continue
for next_node, _dist in road_dict[node].items() :
next_dist = dist + _dist
if dist_lst[next_node] > next_dist :
dist_lst[next_node] = next_dist
heappush(q, (next_dist, next_node))
return dist_lst
def remove_min_route(S, D, dist_lst, road_dict, rev_road_dict) :
remove_lst = list()
q = deque([D])
while q :
cur = q.popleft()
if cur == S :
continue
for prev, dist in rev_road_dict[cur] :
if dist_lst[prev] + dist == dist_lst[cur] and (prev, cur) not in remove_lst :
remove_lst.append((prev, cur))
q.append(prev)
for prev, cur in remove_lst :
del road_dict[prev][cur]
def solve() :
while True:
N, M = map(int, input().split())
if N == M == 0 :
return
S, D, road_dict, rev_road_dict = make_road_dict(N, M)
dist_lst = dijkstra(S, D, N, road_dict)
if dist_lst[D] == MAX :
print(-1)
continue
remove_min_route(S, D, dist_lst, road_dict, rev_road_dict)
dist_lst = dijkstra(S, D, N, road_dict)
print(dist_lst[D] if dist_lst[D] < MAX else -1)
solve()
