[백준/python]2982번 국왕의 방문 - 다익스트라

출처 - https://www.acmicpc.net/problem/2982

로직은 쉽게 생각할 수 있는 다익스트라 문제였다. 다만 국왕이 도로를 점유하고 있는 상황을 표현하는 방법이 조금 까다로웠다. 메모리를 비효율적으로 사용하더라도 우선 풀어야겠다고 생각했다. 인접 행렬과 인접 리스트를 모두 사용하여 국왕의 위치를 표시했다.

1. 풀이

• path[u][v]에 u에서 v로 국왕이 이동을 시작한 시간, 도착한 시간을 저장한다. 양방향 그래프이므로 방향과 관계 없이 path[u][v], path[v][u]를 똑같은 값으로 저장한다.
• 다익스트라에서 출발 지점의 초기 거리값을 K로 갱신하여 국왕이 이동하는 시간과 동기화할 수 있다. 이후 도착 시간에서 K를 빼면 이동 시간을 구할 수 있다.
• 다익스트라를 수행하며 현재 노드(node), 다음 노드(next) 사이를 국왕이 지나간 시간을 확인한다. path[node][next] = 출발시간, 도착시간
• 만약 내가 node에 도착한 시간이 출발시간과 도착시간 사이에 있다면 나의 출발 시간을 국왕의 도착시간으로 갱신한다.
• 다익스트라가 종료되면 B에 도착한 최소 시간에서 출발 시간인 K를 빼고 출력한다.

2. 코드

# boj-2982.py
from heapq import heappop, heappush

N,M = map(int, input().split())
A,B,K,G = map(int, input().split())
king = list(map(int, input().split()))
graph =  [ [] for _ in range(N+1) ]
graph2= [ [0 for _ in range(N+1)] for _ in range(N+1) ]
for _ in range(M):
    u,v,w = map(int, input().split())
    graph[u].append([v,w])
    graph[v].append([u,w])
    graph2[u][v] = w
    graph2[v][u] = w
    
path = [ [ [-1,-1] for _ in range(N+1)] for _ in range(N+1) ]
time = 0
for i in range(1, G):
    before = king[i-1]
    node = king[i]
    path[before][node] = time, time + graph2[before][node]
    path[node][before] = time, time + graph2[before][node]
    time += graph2[before][node]

dist = [float('inf') for _ in range(N+1)]
dist[A]=K
heap = [[K,A]]

while heap:
    cost, node = heappop(heap)
    
    if dist[node] < cost :
        continue
        
    for next, weight in graph[node]:
        
        my_start= cost
        king_start, king_end = path[node][next]
        if king_start<=my_start<=king_end :
            my_start = king_end
        
        if dist[next] > my_start+weight :
            dist[next] = my_start+weight
            heappush(heap, [dist[next], next])

print(dist[B]-K)

2.2 코드(오답)

아래와 같이 인접 리스트만 이용하여 풀었지만 51퍼센트에서 틀렸다. 왜 그런지 아직도 모르겠다.

# boj-2982.py
from heapq import heappop, heappush

N,M = map(int, input().split())
A,B,K,G = map(int, input().split())
king = list(map(int, input().split()))
graph =  [ [] for _ in range(N+1) ]
for _ in range(M):
    u,v,w = map(int, input().split())
    graph[u].append([v,w])
    graph[v].append([u,w])
    
path = [[-1,-1]for _ in range(N+1)]
if G>=1:
    path[king[0]] = [0,0]
    time = 0
    for i in range(1, len(king)):
        node = king[i]
        before = king[i-1]
    
        for next, cost in graph[before]:
            if next== node:
                time += cost
                #어디서 왔는지?, 여기서 다시 출발 시간 언제야? (여기 도착시간)
                path[node] = [before, time]
                break

dist = [float('inf') for _ in range(N+1)]
dist[A]=K
heap = [[K,A]]

while heap:
    cost, node = heappop(heap)
    if dist[node] < cost :
        continue
        
    for next, weight in graph[node]:
        
        my_start,my_end = cost, cost+weight
        #내 출발 지점과 왕 출발지점 같을 때
        if path[next][0] ==node :
            king_start, king_end = path[node][1], path[next][1]
            if king_start<=my_start<king_end :
                my_start = king_end

        #내 출발지점과 왕의 도착 지점이 같을 때
        elif path[node][0] ==next:
            king_start, king_end = path[next][1], path[node][1]
            if king_start<=my_start<king_end:
                my_start = king_end

            
        if dist[next] > my_start+weight :
            dist[next] = my_start+weight
            heappush(heap, [dist[next], next])

print(dist[B]-K)