[코딩 테스트 연습(파이썬/Python)] 백준(BOJ) 5719번 _ 거의 최단 경로

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

5719번: 거의 최단 경로

[문제]

요즘 많은 자동차에서는 GPS 네비게이션 장비가 설치되어 있다. 네비게이션은 사용자가 입력한 출발점과 도착점 사이의 최단 경로를 검색해 준다. 하지만, 교통 상황을 고려하지 않고 최단 경로를 검색하는 경우에는 극심한 교통 정체를 경험할 수 있다.

상근이는 오직 자기 자신만 사용 가능한 네비게이션을 만들고 있다. 이 네비게이션은 절대로 최단 경로를 찾아주지 않는다. 항상 거의 최단 경로를 찾아준다.

거의 최단 경로란 최단 경로에 포함되지 않는 도로로만 이루어진 경로 중 가장 짧은 것을 말한다. 

예를 들어, 도로 지도가 아래와 같을 때를 생각해보자. 원은 장소를 의미하고, 선은 단방향 도로를 나타낸다. 시작점은 S, 도착점은 D로 표시되어 있다. 굵은 선은 최단 경로를 나타낸다. (아래 그림에 최단 경로는 두 개가 있다)거의 최단 경로는 점선으로 표시된 경로이다. 이 경로는 최단 경로에 포함되지 않은 도로로 이루어진 경로 중 가장 짧은 경로이다. 거의 최단 경로는 여러 개 존재할 수도 있다. 예를 들어, 아래 그림의 길이가 3인 도로의 길이가 1이라면, 거의 최단 경로는 두 개가 된다. 또, 거의 최단 경로가 없는 경우도 있다.

[입력]

입력은 여러 개의 테스트 케이스로 이루어져 있다. 각 테스트 케이스의 첫째 줄에는 장소의 수 N (2 ≤ N ≤ 500)과 도로의 수 M (1 ≤ M ≤ 10**4)가 주어진다. 장소는 0부터 N-1번까지 번호가 매겨져 있다. 둘째 줄에는 시작점 S와 도착점 D가 주어진다. (S ≠ D; 0 ≤ S, D < N) 다음 M개 줄에는 도로의 정보 U, V, P가 주어진다. (U ≠ V ; 0 ≤ U, V < N; 1 ≤ P ≤ 103) 이 뜻은 U에서 V로 가는 도로의 길이가 P라는 뜻이다. U에서 V로 가는 도로는 최대 한 개이다. 또, U에서 V로 가는 도로와 V에서 U로 가는 도로는 다른 도로이다.

입력의 마지막 줄에는 0이 두 개 주어진다.

[출력]

각 테스트 케이스에 대해서, 거의 최단 경로의 길이를 출력한다. 만약, 거의 최단 경로가 없는 경우에는 -1을 출력한다.

 

[아이디어]

1) 다익스트라를 통해 최단 거리를 구한다.

2) 최단 거리를 만들어내는 간선들을 bfs를 통해 방문처리한다.

3) 방문처리 되지 않은 간선들만 이용해 다시 다익스트라를 시도해, 거리가 갱신되면 그 최소를 그렇지 않으면 -1을 출력한다.

 

import heapq
from collections import deque
def dijk(s,e,dist,INF):
    q = []
    heapq.heappush(q,(0,s))
    dist[s] = 0
    while q:
        d, now = heapq.heappop(q)
        if dist[now] < d:
            continue
        for x in g[now]:
            if not visit[now][x[0]]:
                cost = d + x[1]
                if cost < dist[x[0]]:
                    dist[x[0]] = cost
                    heapq.heappush(q,(cost,x[0]))
    return dist[e] if dist[e]!=INF else -1

def bfs(s,e):
    q = deque([e])
    while q:
        n = q.popleft()
        for x,w in back[n]:
            if dist[x]+w==dist[n] and not visit[x][n]:
                visit[x][n]=1
                q.append(x)
while True:
    n,m=map(int,input().split())
    if n==0: break
    s,e = map(int,input().split())
    g = [[] for _ in range(n)]
    back = [[] for _ in range(n)]
    INF = int(1e9)
    dist = [INF]*n
    for _ in range(m):
        a,b,c = map(int,input().split())
        g[a].append((b,c))
        back[b].append((a,c))
    visit = [[0]*n for _ in range(n)]
    dijk(s,e,dist,INF)
    bfs(s,e)
    dist = [INF]*n
    print(dijk(s,e,dist,INF))

효율성을 추구한답시고 목적지에 도착했을 때 continue를 해야하는 걸 break 했다가 83%에서 틀렸습니다를 봤다. 다익스트라야 노드 사이의 간선이 최대 1개이고 목적지까지의 최단거리만 구하므로 상관없지만, bfs의 경우 최단 거리인 경로가 여러 개일 수 있기 때문에 break가 아니라 continue 처리 해주어야한다. (q에 남아있는 점이 있을 수 있으므로) 이 문제의 경우 해당 continue문을 추가하지 않고 전체에 대해 돌려도 시간이 넉넉하다.