[테스트케이스 모음] 백준 5719번: 거의 최단 경로 Index Error 와 시간초과 에러 해결 python, 파이썬

1. 문제

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

5719번: 거의 최단 경로

 

 

 

2. 풀이

1) 모든 점에 대해 최단거리 값을 구한다. (dijkstra)

2) 목표 지점 D의 최단거리 값을 기준으로 bfs를 통해 경로를 추적한다.

여기서 경로를 추적한다는 말은 ' cur 다익스트라값 - 탐색하는 점(pos)와 (cur)사이 cost == pos의 다익스트라값' 을 의미한다.

3) 이렇게 삭제해야할 점들을 set에 넣어 중복되지 않게 한다.

4) 이 간선들을 삭제한다. ( ✔ Index Error가 날 수 있으므로 array에 삭제할 간선은 표시하지 않으며 graph를 표현하고 이걸 바탕으로 그래프로 만든다. )

5) 이제 원래 최단거리 간선들이 없는 상태로 최단거리를 구한다.

6) 최단거리가 있다면 그 값을, 아니면 (업데이트가 안되있으므로 math.inf 상태이다) -1을 출력한다.

 

기본적인 풀이가 이렇고,

사실 에러가 정말 많이 났다.

 

1. Index Error는 간선을 삭제하는 코드에서 났다.

원소를 삭제하면 iteration이 없었던 것으로 된다.

삭제할 것을 array에 표현 한 뒤 graph로 옮기는 것을 선택했다.

  adj = [[-1 for i in range(N)] for j in range(N)]
  gph_=[[] for _ in range(N)]
  
  for u,v in s:
    adj[u][v]=-1
  for i in range(N):
    for j in range(N):
      if adj[i][j]!=-1:
        gph_[i].append((j,adj[i][j]))

 

2) 시간 초과는 bfs에서 visit을 하지 않아서 났다.

탐색한 간선을 또 탐색한다.

visit을 2차원을 만들어서 방향을 표시해줬다. 1차원으로 만들면 모든 간선을 삭제하지 않는다.

  visit=[[-1 for _ in range(N)] for __ in range(N)]
  q=deque()
  s=set()
  q.append(D)
  
  while q:
    cur = q.popleft()
    for (p,c) in back_gph[cur]:
      if visit[cur][p]==1: # 방문했던 방향의 간선이면 지나간다.
        continue
      if res_lis[cur] == res_lis[p]+c: # 최소간선이라는 것을 확인하면
        s.add((p,cur)) # set에 삭제할 간선 목록에 넣는다
        q.append(p)
        if p==S: # 탐색하는 것이 시작정점이라면 그냥 통과한다. 그래야 다른 최소거리 간선들도 다 볼 수 있다.
          continue
        else:
          visit[cur][p]=1 # 방문을 표시한다

 

 

 

 

3. 구현

import sys
import heapq
import math
from collections import deque
sys.setrecursionlimit(1000000)

# sys.stdin = open("almost.in")
sys.stdin = open("input.txt")

# 다익스트라
def dijk(node, gph):

  dist=[math.inf for _ in range(N+2)]
  edges=[]

  dist[node] = 0
  heapq.heappush(edges,(dist[node], node))

  while edges:
    cost, pos = heapq.heappop(edges)
    if dist[pos]<cost:
      continue
    for p,c in gph[pos]:
      c+=cost
      if dist[p]>c:
        dist[p]=c
        heapq.heappush(edges,(c, p))
  return dist

while True:
  N, M = map(int, sys.stdin.readline().split())
  if (N,M)==(0,0):
    break
  S, D = map(int, sys.stdin.readline().split())

  dist=[math.inf for _ in range(N+2)]
  edges=[]
  gph=[[] for _ in range(N)]
  back_gph=[[] for _ in range(N)]
  adj = [[-1 for i in range(N)] for j in range(N)]

  while M:
    M-=1
    u,v,p = map(int, sys.stdin.readline().split())
    # 원래그래프
    gph[u].append((v,p))
    #경로를 확인할 역그래프
    back_gph[v].append((u,p))
    # 그래프를 지울 때 쓸 array
    adj[u][v]=p

  res_lis = dijk(S,gph)
  res =res_lis[D]
	
  # bfs에서 중복 탐색을 제거할 visit
  visit=[[-1 for _ in range(N)] for __ in range(N)]
  q=deque()
  s=set()
  q.append(D)
  
  #bfs
  while q:
    cur = q.popleft()
    for (p,c) in back_gph[cur]:
      if visit[cur][p]==1:
        continue
      if res_lis[cur] == res_lis[p]+c:
        s.add((p,cur)) # 바로 gph에 사용할 수 있게! 순서를 바꿔 원래 그래프의 from to 방향대로 넣음
        q.append(p)
        if p==S:
          continue
        else:
          visit[cur][p]=1
  
  #삭제하고 gph_에 넣어 다시 dijkstra에 넣는다
  gph_=[[] for _ in range(N)]
  for u,v in s:
    adj[u][v]=-1
  for i in range(N):
    for j in range(N):
      if adj[i][j]!=-1:
        gph_[i].append((j,adj[i][j]))

  res_lis = dijk(S,gph_)

  # D에 도달한 적이 없으면 -1 아니면 value를 print한다.
  if res_lis[D] == math.inf:
    print(-1)
  else:
    print(res_lis[D])

 

 

 

 

4. 테스트케이스 (백준 테케 정리)

이번 문제는 백준에 테케 올라온 것들을 정리했다.

예리한 예시들이 많아서 큰 도움이 되었다.

따옴표 안에 있는 말은 테케 올려주신 분들이 어떤 점을 확인하면 좋은 지 말해주신 것을 인용.

 

4 5
0 2
0 1 1
0 3 5
1 2 2
1 3 1
3 2 1
0 0

답: -1

최단경로가 다 지워지지 않으면 6, 다 지워지면 -1이 나온다.

4 개의 간선을 지워야한다.

 

 

5 6
0 4
0 1 2
0 2 2
1 2 1
2 4 2
2 3 1
3 4 2

답: 6
" 최단경로에 포함되는 정점을 전부 패스해버리면 안됨 "

 

 

5 8
0 4
0 1 1
0 2 1
1 3 1
2 3 1
3 4 1
0 4 6
1 4 4
2 4 4
0 0

답: 6

" 마지막 지점에서는 들어오는 루트를 모두 제거하는데
중간 노드는 하나씩만 제거 "

 

 

3 1
0 2
0 1 1
3 2
0 2
1 2 1
0 2 1
0 0

" 90번째 줄에 들어간 경우에 adj가 초기화되지 않음 "

답: -1 -1

 

 

5 6
0 4
0 1 10
0 2 1
2 1 2
1 3 1
3 4 2
1 4 5
0 0

답: 15 

" 시작점 s와 도착점  e, 그 사이의 정점 x, y가 있을 때
s -> x -> y -> e
같은 그래프에서 
(s->y 까지의 최단거리 + y->e 까지의 최단거리) == (s -> e까지의 최단거리)
일때 단순히 x -> y를 최단경로에 포함된 간선으로 처리합니다.
따라서 아래 데이터처럼 돌아가는 길이 최단경로인 경우에는 틀려야하는데 채점결과 ac가 뜹니다. "

 

 

6 8 
0 5
0 1 1
1 2 1
2 3 1
3 4 1
4 5 1
0 2 2
2 5 10
0 5 5
0 0

답 -1