1 minute read

문제

접근 방법

거의 최단 경로란 최단 경로에 포함되지 않는 도로로만 이루어진 경로이기 때문에 최단 경로를 구성하는 경로들을 우선 구해야 한다. 최단 경로를 구성하는 경로들을 모두 제거한 뒤, 다시 최단 거리를 구하여 거의 최단 경로를 구하고자 하였다.

시작점에서 도착점까지의 최단 거리를 우선 구해야 하기 때문에 Dijkstra 알고리즘을 생각했다. 그렇다면 최단 경로를 어떻게 다 구할 것인가.

도착점으로 갈 수 있는 노드(node)로 갈 수 있는 최단 거리 fastest[node] == 시작점->임의의 노드(i)까지의 최단 거리 (fastest[i]) + i에서 도착점까지 갈 수 있는 노드 (node)까지의 거리

를 만족한다면 최단 경로를 구성한다고 생각하였다. 이 노드들을 다 탐색하기 위해서는 그래프 탐색 알고리즘을 사용해야 했고 이 조건을 만족하는 간선들을 다 없애기 편하기 위해서 인접 행렬로 graph를 구현하였다.

최단 경로를 구성하는 경로들을 모두 제거하고나서 다시 dijkstra를 하여 거의 최단 경로를 구하였다.

정답 코드

import sys
import heapq
from collections import deque
input = sys.stdin.readline

"""
거의 최단 경로를 구하기 위해서는 최단 경로를 구성하는 간선들을 모두 제거해야 한다.

간선들을 제거하기 위해서는 그래프를 인접 행렬로 하는 것이 나아보임
"""

while True:
  n,m = map(int,input().split())
  if n==0 and m==0:
    break

  graph = [[0]*(n) for _ in range(n)]
  
  start,dest = map(int,input().split())
  
  for _ in range(m):
    u,v,p = map(int,input().split())
    graph[u][v] = p

  def dijkstra(s,d):
    q = []
    heapq.heappush(q, (0,s))
    distances = [int(1e9)]*n
    distances[s] = 0

    while q:
      mid_dist, mid = heapq.heappop(q)
      if distances[mid] < mid_dist:
        continue

      for i in range(n):
        #mid와 adjacent한 노드들 구하기 (인접행렬을 사용해서 이렇게 dijkstra를 하였다.)
        if graph[mid][i]!=0:
          end_dist = graph[mid][i]
          end = i
          new_dist = mid_dist + end_dist
          
          if new_dist < distances[end]:
            distances[end] = new_dist
            heapq.heappush(q, (new_dist, end))
            
    return distances
    
  fastest = dijkstra(start, dest)

  #역추적: fastest[end] = fastest[other] + graph[other][end] 라면 그 경로는 최단 경로

  
  # 도착 지점에서 bfs를 시작
  def bfs(s):
    q = deque()
    visited = set()
    visited.add(s)
    q.append(s)
    while q:
      node = q.popleft()
      for i in range(n):
        #i -> node 경로가 존재할 때
        if graph[i][node] != 0 and fastest[node] == fastest[i] + graph[i][node]:
          # 이게 최단 경로라면
          #이 간선 제거
          graph[i][node] = 0

          if i not in visited:
            q.append(i)
            visited.add(i)

  bfs(dest)
  
  
  #다시 최단 경로 구하기 -> 이 경로가 거의 최단 경로
  almost_fastest = dijkstra(start, dest)
  if almost_fastest[dest]!=int(1e9):
    print(almost_fastest[dest])
  else:
    print(-1)

You May Also Enjoy