[백준 5719번] 거의 최단 경로 (Python3)

import sys
input = sys.stdin.readline
from heapq import heappush, heappop
from collections import deque
INF = 10**9

def Djikstra():
  DP = [INF]*N
  
  hq = []
  hq.append((0,start,start))
  while hq:
    w,now,last = heappop(hq)
    if DP[now] < w:
      continue
    if DP[now] == w:
      path[now].append(last)
      continue
    DP[now] = w
    path[now] = [last]
    for next in range(N):
      w1 = graph[now][next]
      if w1 != INF:
        hq.append((w+w1,next,now))

  return DP[end]

def delete():
  dq = deque([(end,end)])
  while dq:
    now,next = dq.popleft()
    if graph[now][next] == INF:
      continue
    graph[now][next] = INF
    for last in path[now]:
      dq.append((last,now))

while True:
  N,M = map(int,input().split())
  if (N,M) == (0,0):
    break
  start,end = map(int,input().split())

  graph = [[INF]*N for i in range(N)]
  graph[end][end] = 0
  for i in range(M):
    x1,x2,w = map(int,input().split())
    graph[x1][x2] = w

  path = {}
  shortest = Djikstra()
  if shortest == INF:
    print(-1)
    continue
  delete()
  short = Djikstra()
  if short == INF:
    print(-1)
  else:
    print(short)

 

기본적인 알고리즘은 떠올리기 매우 쉽다.

간단하게 요약하면

 

1. 다 익스트라로 최단거리 탐색, 이때 최단거리의 경로까지 저장해주어야 한다.

2. 저장된 최단거리 경로의 간선 삭제

3. 다 익스트라로 최단거리 탐색 (거의 최단경로)

 

 

여기까지는 누구나 떠올릴 수 있지만, 실수할 수 있는 포인트가 매우 많았다. 내가 한 실수들을 정리하면

1. 다 익스트라를 한번써서 경로를 한개 지우고, 다익스트라 한번 더 써서 이전의 거리와 같으면 경로 한개 더 지우고 하는 식으로는 풀 수 없다. 모든 최단 경로를 한번에 다 찾아야한다.

(이유: 시간초과도 문제이지만 최단경로들이 노선을 공유하는 경우 모든 최단경로를 지울 수 없다.)

2. BFS 하는 과정에서 지나간 곳인지 check하지 않으면 메모리초과 or 시간초과가 발생한다.

(이유 : 같은 노선을 공유하는 경우 중복해서 실행됨)

3. check하기 위해서 visited 리스트를 사용한다면 1차원 리스트로 만들어선 안된다. 그러면 해당 노드를 지나는 서로 다른 간선을 모두 지울 수 없다.

4. BFS 도중 시작지점이 나왔다고 해서 함수를 끝내선 안된다. 모든 노선을 지울 수 없다.

 

대략 이 정도가 될 것이다.

 

 

계속해서 틀렸습니다 가 나와서 짜증나는 문제였지만 BFS와 다 익스트라에 대해서 좀 더 깊은 이해를 할 수 있게된 문제였던 것 같다.

 

 

오늘의 교훈) BFS에서 지나온 곳을 항상 체크하자