[Baekjoon] 5719번 : 거의 최단 경로
1. 문제
https://www.acmicpc.net/problem/5719
- 다익스트라 문제
// 문제
요즘 많은 자동차에서는 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을 출력한다.
// 예제 입력 1
7 9
0 6
0 1 1
0 2 1
0 3 2
0 4 3
1 5 2
2 6 4
3 6 2
4 6 4
5 6 1
4 6
0 2
0 1 1
1 2 1
1 3 1
3 2 1
2 0 3
3 0 2
6 8
0 1
0 1 1
0 2 2
0 3 3
2 5 3
3 4 2
4 1 1
5 1 1
3 0 1
0 0
// 예제 출력 1
5
-1
6
2. 핵심 아이디어
- 다익스트라 최단 경로 알고리즘을 수행
- 다익스트라 최단 경로에 포함되는 모든 간선을 추적
- 초기 최단 경로에 포함된 간선을 제외한 뒤에, 다시 최단 경로를 탐색
3. Python 문제풀이
import sys
import heapq
from collections import deque
input = sys.stdin.readline
def dijkstra() :
heap_data = []
heapq.heappush(heap_data, (0, start))
distance[start] = 0
while heap_data :
dist, now = heapq.heappop(heap_data)
if distance[now] < dist :
continue
for i in adj[now] :
cost = dist + i[1]
if distance[i[0]] > cost and not dropped[now][i[0]] :
distance[i[0]] = cost
heapq.heappush(heap_data, (cost, i[0]))
def bfs() :
q = deque()
q.append(end)
while q :
now = q.popleft()
if now == start :
continue
for prev, cost in reverse_adj[now] :
if distance[now] == distance[prev] + cost :
dropped[prev][now] = True
q.append(prev)
while True :
n, m = map(int, input().split())
if n == 0 :
break
start, end = map(int, input().split())
adj = [[] for _ in range(n + 1)]
reverse_adj = [[] for _ in range(n + 1)]
for _ in range(m) :
x, y, cost = map(int, input().split())
adj[x].append((y, cost))
reverse_adj[y].append((x, cost))
dropped = [[False] * (n + 1) for _ in range(n + 1)]
distance = [1e9] * (n + 1)
dijkstra()
bfs()
distance = [1e9] * (n + 1)
dijkstra()
if distance[end] != 1e9 :
print(distance[end])
else :
print(-1)
# ------------------------------------------------------------------
from collections import deque
import sys
import heapq
INF = 1e9
def dijkstra():
q = []
heapq.heappush(q, (0, s))
distance[s] = 0 # 출발지
while q: # 큐가 비어있지 않다면
dist, now = heapq.heappop(q)
# 현재 노드가 이미 처리된 적이 있는 노드라면 무시
if distance[now] < dist:
continue
# 현재 노드와 연결된 다른 인접한 노드들을 확인하면서 거리 업데이트
for i in graph[now]:
cost = dist + graph[now][i]
if cost < distance[i]: # 해당 지점을 거치는 것이 거리가 짧은 경우
distance[i] = cost
heapq.heappush(q, (cost, i))
def bfs():
q = deque()
q.append(d)
while q:
v = q.popleft()
if v == s: # 시작점 도달
continue # break하면 다른 최단 경로를 확인할 수 없다.
for pre_v, pre_c in r_graph[v]:
if distance[pre_v] + graph[pre_v][v] == distance[v]:
if (pre_v, v) not in remove_List:
remove_List.append((pre_v, v))
q.append(pre_v)
if __name__ == "__main__":
while True:
n, m = map(int, sys.stdin.readline().split())
if n == 0 and m == 0: # n과 m이 0이면 종료
break
s, d = map(int, sys.stdin.readline().split()) # 출발지, 도착지
graph = [dict() for _ in range(n)]
r_graph = [[] for _ in range(n)]
for _ in range(m):
u, v, p = map(int, sys.stdin.readline().split()) # 도로 정보 입력
graph[u][v] = p
r_graph[v].append((u, p)) # 경로를 추적하기 위해서 역순 저장
# 다익스트라 알고리즘을 사용하여 최단 거리 찾기
distance = [INF] * n
dijkstra()
# BFS를 사용하여 최단 경로 추적
remove_List = list()
bfs()
# 최단 경로 제거
for u, v in remove_List:
del graph[u][v]
# 다익스트라 알고리즘을 사용하여 최종 최단 경로 찾기
distance = [INF] * n
dijkstra()
if distance[d] == INF: # 거의 최단 경로가 없는 경우
print(-1)
else:
print(distance[d])
4. Java 문제풀이
댓글남기기