-
[Python 3] BOJ - 5719 "거의 최단 경로"BOJ 2021. 10. 19. 22:30
# 문제 링크
https://www.acmicpc.net/problem/5719
# 풀이
개인적으로 이 문제의 핵심은 다익스트라와 인접 리스트를 역순으로 뒤집는 것이라 생각한다. 시작점에서 출발하여 끝점까지의 최단 경로는 여러 개 존재할 수 있기 때문에 실제 최단 경로를 찾으려 들면 시간초과를 피할 수 없을 것이다. 그런데 최단 경로라는 점을 생각했을 때 최단 경로 상에 있는 간선의 가중치의 합은 곧 끝점의 최단 거리와 같다.
위 그림 1에서는 원래 인접 리스트의 방향이 반대인 역인접 리스트와 시작점에서 출발하여 각 점까지의 최단 거리 배열을 나타내고 있다. 이 때 임의의 한 점과 연결된 간선들 중에서 최단 경로 상의 간선을 찾는 방법은 임의의 한 점과 간선으로 연결된 정점의 최단거리에서 현재점까지의 거리의 차이가 간선의 길이와 일치 여부로 알 수 있다.
예를 들어 위 그림 1에서 현재점이 6이라고 하자. 따라서, 6과 연결된 정점들은 2,3,4,5이다. 그런데 (2, 6)의 간선의 경우는 만약에 이 간선이 정말로 최단 경로 상의 간선이었다면 현재 D[2]에서 간선의 가중치인 4를 더한 5가 D[6]과 같아야 한다. 그런데 그렇지 않으므로 (2, 6)의 간선은 절대로 최단 경로 상의 간선이 될 수 없음은 자명하다. 이 논리에 의해 (3, 6), (5, 6)의 간선이 최단 경로 상의 간선임을 알 수 있다. 이렇게 계속 최단 경로 상의 간선을 탐색하다가 연결된 정점이 시작점이라면 탐색을 종료한다.
위 작업이 끝나고 나면 최단 경로 상의 간선을 모두 지울 수 있고 지워진 간선들로 시작점에서 끝점까지의 최단 경로를 문제의 요구에 맞게 출력하면 정답을 구할 수 있다.
# 코드
import heapq, sys # dijkstra1 : 현재 정점 v에서 출발하여 각 정점의 최단거리를 갱신하는 함수 def dijstra1(v): d[v] = 0 q = [] q.append((0, v)) while q: cur_dist, cur = heapq.heappop(q) if d[cur] < cur_dist: continue for (next, next_dist) in adj[cur]: # 다익스트라 갱신 조건을 만족하면서 현재 간선이 최단 경로가 아닌 경우 if next_dist + cur_dist < d[next] and check[cur][next] == False: d[next] = next_dist + cur_dist heapq.heappush(q, (next_dist + cur_dist, next)) # dijkstra2 : 현재 정점 v에서 출발하여 최단 경로 간선을 지우는 함수 def dijstra2(v): q = [] q.append((d[v], v)) while q: cur_dist, cur = heapq.heappop(q) # 현재점이 시작점이면 탐색 종료 if cur == s: continue for (past, past_dist) in rev_adj[cur]: # 이미 최단 경로라면 탐색 종료 if check[past][cur] == True: continue # 최단 경로 상의 간선인 경우 if d[past] == d[cur] - past_dist: check[past][cur] = True heapq.heappush(q, (d[past], past)) INF = 9876543210 while True: # 입력부 n, m = map(int, sys.stdin.readline().split()) if n == 0 and m == 0: break s, e = map(int, sys.stdin.readline().split()) # adj : 일반적 인접리스트 # rev_adj : 방향을 바꾼 역인접리스트 adj = [[] for _ in range(n)] rev_adj = [[] for _ in range(n)] # check : (i, j)를 잇는 간선이 최단 경로 상에 있는 간선인지 아닌지 나타내는 2차원 배열 check = [[False] * n for _ in range(n)] # d : 시작점에서 출발하여 각 점의 최단거리를 저장하는 배열 d = [INF] * n for i in range(m): a, b, c = map(int, sys.stdin.readline().split()) adj[a].append((b, c)) rev_adj[b].append((a, c)) # 첫 다익스트라1로 d 갱신 dijstra1(s) # 이후 다익스트라2로 check 갱신 dijstra2(e) # 거리 배열 초기화 후 두번째 다익스트라로 최단 경로 상의 간선을 배제한 최단 경로 갱신 for i in range(n): d[i] = INF dijstra1(s) # 문제의 조건에 따라 정답 출력 print(d[e] if d[e] != INF else -1)
'BOJ' 카테고리의 다른 글
[Python 3] BOJ - 21757 "나누기" (0) 2021.10.29 [Python 3] BOJ - 2786 "상근이의 레스토랑" (0) 2021.10.25 [Python 3] BOJ - 1581 "락스타 락동호" (0) 2021.10.16 [Python 3] BOJ - 17090 "미로 탈출하기" (0) 2021.10.15 [Python 3] BOJ - 1944 "복제 로봇" (0) 2021.10.10