[백준] 2307. 다익스트라_도로검문 - Python

문제

그림 1은 어떤 도시의 주요 지점과 그 지점들 간의 이동시간을 나타낸 그래프이다. 그래프의 노드는 주요 지점을 나타내고  두 지점을 연결한 도로(에지)에 표시된 수는 그 도로로 이동할 때 걸리는 분 단위의 시간을 나타낸다. 두 지점 a와 b를 연결하는 도로는 도로(a,b)로 표시한다.

예를 들어 도로(1,2)와 도로(2,3)를 통하여 지점1에서 지점3으로 갈 때 걸리는 시간은 3분이다. 도로는 모두 양방향이라고 가정하므로 도로(a,b)와 도로(b,a)를 지날 때 걸리는 시간은 항상 같다고 한다.

오세준은 입력 데이터에 표시된 도시로 진입하여 이 도시를 가장 빠른 시간 내에 빠져나가고자 한다. 그런데 이 사실을 알고 있는 류원룡이 어떤 하나의 도로(에지)를 선택하여 이 도로에서 검문을 하려고 한다. 따라서 오세준은 이 도로를 피해서 가장 빠르게 도시를 탈출하고자 한다. 이 경우 류원룡이 검문을 위하여 선택하는 도로에 따라서 오세준의 가장 빠른 탈출시간은 검문이 없을 때에 비하여 더 늘어날 수 있다.

문제는 도로검문을 통하여 얻을 수 있는 탈출의 최대 지연시간을 계산하는 것이다. 추가설명은 다음과 같다.

1. 두 개의 지점을 직접 연결하는 도로가 있는 경우, 그 도로는 유일하다. 
2. 도시의 지점(노드)은 1에서 N번까지  N개의 연속된 정수로 표시된다.
3. 오세준이 도시에 진입하는 지점은  항상 1번이고 도시를 빠져 나가기 위하여 최종적으로 도달해야하는 지점은 항상 N번 지점이다.
4. 오세준은 검문을 피해서 가장  빨리 도시를 빠져나가고자 하고, 류원룡은 적절한 도로를 선택하여 이 오세준들의 탈출시간을 최대한 지연시키고자 한다.
5. 각 도시 지점 간을 이동하는 시간은 항상 양의 정수이다.

입력 도시의 도로망에 따라서 류원룡이 어떤 도로를 막으면 오세준은 도시를 탈출하지 못할 수도 있다. 이 경우 검문으로 인하여 지연시킬 수 있는 탈출시간은 무한대이다. 이 경우에는 -1을 출력해야 한다.

그림 1에서 볼 때 검문이 없을 경우 오세준이 도시를 탈출하는데 걸리는 시간은 4분이다. 만일 류원룡이 도로(4,3)을 막으면 그 탈출시간을 지연시킬 수 없으므로 지연시간은 0이다. 만일 도로(2,3)을 막으면, 오세준들이 가장 빠르게 탈출할 수 있는 시간은 5분이므로 탈출지연시간은 1분이고, 도로(3,6)을 막으면 탈출지연시간은 2분이다.

여러분은 입력 데이터에 표시된 도로망을 읽고, 류원룡이 한 도로를 막고 검문함으로써 지연시킬 수 있는 최대시간을 정수로 출력하여야한다. 만일 지연효과가 없으면 0을 출력해야하고, 도시를 빠져나가지 못하게 만들 수 있으면(지연시간이 무한대) -1을 출력해야 한다.

입력

첫 줄에는 지점의 수를 나타내는 정수  N(6 ≤ N ≤ 1000)과 도로의 수 M(6 ≤ M ≤ 5000)이 주어진다. 그 다음 이어 나오는 M개의 각 줄에는 도로(a, b)와 그 통과시간 t가 a b t 로 표시된다. 단 이 경우 a < b 이고 1 ≤ t ≤ 10000이다.

출력

경찰이 하나의 도로를 막음으로써 지연시킬 수 있는 최대 시간을 정수로 출력한다. (단, 그 지연시간이 무한대이면 -1을 출력해야 한다.)

 

-----------------------------------------------------------------------------------------------------------------------------------

 

★ 시작하기 전에

다익스트라는 맞는데, 문제가 이해가 안간다.처음에 최단시간은 다익스트라 기본형으로 풀어서 정답을 만들 수 있고, 만약 검문을 하게 된다면....노드와 노드를 연결하는 선 중 하나씩제거하면서 다시 다익스트라 함수를 돌려서 걸리는 시간을 구하고 그 차이가 가장 큰 것을 답으로 정하면 된다..근데 전체 노드를 다 하나씩 돌다보니까... 시간초과가 계속 발생하게 된다....

 

해결법. 처음 검문을 하지 않을때 지나가는 경로만을 하나씩 제거해보면 된다.

왜? 다른 경로를 선택한다면, 기존 검문을 하지 않을때로가 가장 빠르게 지나가기에 영향을 주지 않기 때문!!!!!

이게 해결책 두가지 이다.

1. 처음 최단경로를 저장한다.

2. 그 선 중 하나씩 사용하지 않으면서 다익스트라를 다시 계산한다.

 

import sys
import heapq

input = sys.stdin.readline

# 다익스트라 함수를 정의한다.
def djt(s, e):
    time = [INF for _ in range(n+1)]
    time[1] = 0
    q = [(0, 1)]
    while q:
        t, now = heapq.heappop(q)
        if now==n: break
        for next, plus in graph[now]:
        	# 이걸 생각해야 한다.
            # s,e는 선택된 노드들로 그 노드들의 경우는 고려하지 않도록 한다.
            # s,e가 선택되면 그곳은 검문소가 되므로 continue해준다.
            if s==now and e==next or s==next and e==now: continue
            if t+plus < time[next]:
                time[next] = t+plus
                # 이부분은 pre함수를 만든다. 처음 다익스트라를 진행할때 pre함수가 만들어진다.
                if not s: pre[next] = now
                heapq.heappush(q, (time[next], next))
    return time[n]

INF = sys.maxsize

# 입력값을 받아온다.
n, m = map(int, input().split())
graph = [[] for _ in range(n+1)]
for _ in range(m):
    a, b, t = map(int, input().split())
    graph[a].append((b,t))
    graph[b].append((a,t))

# 이 부분이 중요!!
# 최단경로로 진행했을 경우, 각 노드(index)에 이전노드(value)로 저장한다.
# 즉, 1번 인덱스에 5가 저장되면 5->1로 노드가 진행하는 최단경로가 존재하는것이다.
# 검문소를 고르는데 사용된다.
pre = [0 for _ in range(n+1)]

# 검문하지 않을때, 최단 시간을 알아낸다.
# 이때, pre 리스트에 정보를 다 기입해둔다.
result = djt(0,0)

ans = -1
e = n

# 끝점부터 시작점으로 돌아오면서 하나씩 검문소로 만들어 본다.
while pre[e]!=0:
    s = pre[e]
    output = djt(s, e)
    # 처음 값과 비교해서 답을 갱신해준다.
    if output != INF:
        diff = output-result
        ans = max(ans, diff)
    else:
        ans = -1
        break
    # 시작점을 다시 끝점으로 바꾸고 다음 경로에 검문소를 만든다.
    e = s
print(ans)