요즘 많은 자동차에서는 GPS 네비게이션 장비가 설치되어 있다. 네비게이션은 사용자가 입력한 출발점과 도착점 사이의 최단 경로를 검색해 준다. 하지만, 교통 상황을 고려하지 않고 최단 경로를 검색하는 경우에는 극심한 교통 정체를 경험할 수 있다.
상근이는 오직 자기 자신만 사용 가능한 네비게이션을 만들고 있다. 이 네비게이션은 절대로 최단 경로를 찾아주지 않는다. 항상 거의 최단 경로를 찾아준다.
거의 최단 경로란 최단 경로에 포함되지 않는 도로로만 이루어진 경로 중 가장 짧은 것을 말한다.
예를 들어, 도로 지도가 아래와 같을 때를 생각해보자. 원은 장소를 의미하고, 선은 단방향 도로를 나타낸다. 시작점은 S, 도착점은 D로 표시되어 있다. 굵은 선은 최단 경로를 나타낸다. (아래 그림에 최단 경로는 두 개가 있다)거의 최단 경로는 점선으로 표시된 경로이다. 이 경로는 최단 경로에 포함되지 않은 도로로 이루어진 경로 중 가장 짧은 경로이다. 거의 최단 경로는 여러 개 존재할 수도 있다. 예를 들어, 아래 그림의 길이가 3인 도로의 길이가 1이라면, 거의 최단 경로는 두 개가 된다. 또, 거의 최단 경로가 없는 경우도 있다.
![](https://blog.kakaocdn.net/dn/bRx326/btr1XQIEYir/vkjBstruXYU36yrlDKrCXK/img.png)
입력
입력은 여러 개의 테스트 케이스로 이루어져 있다. 각 테스트 케이스의 첫째 줄에는 장소의 수 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. 코드
import sys
from heapq import heappop, heappush
INF = sys.maxsize
input = sys.stdin.readline
def dijstra(start):
dis[start] = 0
queue = []
heappush(queue, (0, start))
while queue:
dist, now = heappop(queue)
if dis[now] < dist:
continue
for i in maps[now]:
cost = dist + i[1]
if cost < dis[i[0]] and not check[now][i[0]]:
dis[i[0]] = cost
heappush(queue, (cost, i[0]))
def dijstra2(start):
queue = []
heappush(queue, (dis[start], start))
while queue:
dist, now = heappop(queue)
if now == s:
continue
for i in reverse_maps[now]:
if check[i[0]][now]:
continue
if dis[i[0]] == dis[now] - i[1]:
check[i[0]][now] = True
heappush(queue, (dis[i[0]], i[0]))
while True:
n, m = map(int, input().split())
if not n and not m:
break
s, e = map(int, input().split())
maps = [[] for _ in range(n)]
reverse_maps = [[] for _ in range(n)]
check = [[False] * n for _ in range(n)]
dis = [INF] * n
for _ in range(m):
u, v, p = map(int, input().split())
maps[u].append((v, p))
reverse_maps[v].append((u, p))
dijstra(s)
dijstra2(e)
for i in range(n):
dis[i] = INF
dijstra(s)
if dis[e] == INF:
print(-1)
else:
print(dis[e])
3. 풀이
1. 시작점 다익스트라 와 도착점 다익스트라의 가중치 합이 동일 하다는 점을 이용한다.
ex)
<그림 1. 예제 1의 첫번째 TC>
위 그림 1에서는 원래 인접 리스트의 방향이 반대인 역인접 리스트와 시작점에서 출발하여 각 점까지의 최단 거리 배열을 나타내고 있다. 이 때 임의의 한 점과 연결된 간선들 중에서 최단 경로 상의 간선을 찾는 방법은 임의의 한 점과 간선으로 연결된 정점의 최단거리에서 현재점까지의 거리의 차이가 간선의 길이와 일치 여부로 알 수 있다.
예를 들어 위 그림 1에서 현재점이 6이라고 하자. 따라서, 6과 연결된 정점들은 2,3,4,5이다. 그런데 (2, 6)의 간선의 경우는 만약에 이 간선이 정말로 최단 경로 상의 간선이었다면 현재 D[2]에서 간선의 가중치인 4를 더한 5가 D[6]과 같아야 한다. 그런데 그렇지 않으므로 (2, 6)의 간선은 절대로 최단 경로 상의 간선이 될 수 없음은 자명하다. 이 논리에 의해 (3, 6), (5, 6)의 간선이 최단 경로 상의 간선임을 알 수 있다. 이렇게 계속 최단 경로 상의 간선을 탐색하다가 연결된 정점이 시작점이라면 탐색을 종료한다.
위 작업이 끝나고 나면 최단 경로 상의 간선을 모두 지울 수 있고 지워진 간선들로 시작점에서 끝점까지의 최단 경로를 문제의 요구에 맞게 출력하면 정답을 구할 수 있다.
'Algorithm > Python' 카테고리의 다른 글
프로그래머스 행렬 테두리 회전하기 (0) | 2023.03.13 |
---|---|
백준 5551번 쇼핑몰 (0) | 2023.03.06 |
백준 2325번 개코 전쟁 (0) | 2023.03.04 |
백준 17270번 연예인은 힘들어 (0) | 2023.03.04 |
프로그래머스 성격 유형 검사 (1) | 2023.03.03 |