[백준 알고리즘] 5719번: 거의 최단 경로 (Python)

https://www.acmicpc.net/problem/5719 

5719번: 거의 최단 경로

 

소스코드

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

def dijkstra():
  q = []
  min_dis = [float('inf') for _ in range(n)]
  hq.heappush(q,[0,s])
  min_dis[s] = 0 

  while q:
    cur_dis,cur_node = hq.heappop(q)

    if min_dis[cur_node] < cur_dis:
      continue
    for next_node,next_dis in graph[cur_node]:
      if visited[cur_node][next_node]:
        continue
      if min_dis[next_node] > cur_dis + next_dis:
        min_dis[next_node] = cur_dis + next_dis
        hq.heappush(q,[min_dis[next_node],next_node])

  return min_dis

def BFS(): # 목적지 -> 출발지 역방향 탐색
  dq = deque()
  dq.append(d)

  while dq:
    cur_node = dq.popleft()

    if cur_node == s: # 출발점에 도착한 경우 
      continue

    for next_node,next_dis in graph_rev[cur_node]:
      if min_dis[next_node] + next_dis == min_dis[cur_node]:
        if not visited[next_node][cur_node]:
          visited[next_node][cur_node] = True
          dq.append(next_node)

while True:
  n,m = map(int,input().split())
  if n == 0 and m == 0:
    break
  s,d = map(int,input().split())
  graph = [[] for _ in range(n)]
  graph_rev = [[] for _ in range(n)]
  visited = [[False for _ in range(n)] for _ in range(n)]
  for _ in range(m):
    a,b,c = map(int,input().split())
    graph[a].append([b,c])
    graph_rev[b].append([a,c])
  
  min_dis = dijkstra()
  BFS()
  min_dis = dijkstra()
  print(min_dis)
  
  if min_dis[d] == float('inf'):
    print(-1)
  else:
    print(min_dis[d])

 

 

풀이

★ 처음엔 최단 경로로 이동할 때 방문했던 정점들을 기록하고, 역방향으로 이동하면서 그 정점을 제외한 나머지 정점들로 다시 다익스트라를 진행하는 방식으로 접근하였습니다. 하지만 그렇게 된다면 모든 배열을 계속해서 방문하기 때문에 메모리 초과 및 시간초과를 만나게 됩니다. 그렇기에 BFS를 통해 방문한 정점들을 한번에 확인해줘야 합니다 !! 

 

★ 먼저 다익스트라를 수행하면서 목적지에 최단 경로로 이동할 수 있는 경로를 확인해줍니다. 이후 BFS를 돌면서 (이 때 역방향으로 돌아야 하기 때문에 bfs를 도는 시작점은 목적지가 됩니다) 최단 경로를 갈 때 방문했던 정점들을 체크해줍니다. 마지막으로 다시 한번 다익스트라를 돌면서 거의 최단 경로를 찾아줍니다 :)