[파이썬] 백준 2982 : 국왕의 방문 (골드2)

[파이썬] 백준 2982 : 국왕의 방문 (골드2)

2982번: 국왕의 방문

---

문제

---

풀이

0. 방향성 생각

• 왕이 이동한 edge에 대해서 양방향으로 이용 불가능한 시간을 dict으로 저장
• 왕이 이동한 간선을 이동할 때, 시간이 겹치는지 안겹치는지 나눠서 풀이

1. 입력

from collections import defaultdict as dd
import heapq as hq
import sys
input = lambda : sys.stdin.readline().rstrip()

node,edge = map(int,input().split())
start,end,diff,path = map(int,input().split())

sequence = list(map(int,input().split()))

costs = dd(dict)
for _ in range(edge):
    a,b,cost = map(int,input().split())
    costs[a][b] = cost
    costs[b][a] = cost

king,t = {},0
for i in range(path-1):
    a,b = sequence[i],sequence[i+1]
    nt = costs[a][b]
    king[(a,b)] = (t,t+nt)
    king[(b,a)] = (t,t+nt)
    t += nt

• costs[a][b] = cost 이런식으로 a to b에서 cost만큼 든다. 양방향으로 추가해주기
• king[(a,b)] = (t1,t2) 이런식으로 a to b 간선 이동 시 이동 불가능한 시간 추가해주기

 

2. 다익스트라 탐색

heap = [(diff,start)]
while heap:

    t,x = hq.heappop(heap)

    if x == end:
        print(t-diff)
        break

    for nx,nt in costs[x].items():

        if (x,nx) in king:
            ks,ke = king[(x,nx)]

            if ks<=t<ke and ke+nt < visit[nx]:
                visit[nx] = ke+nt
                hq.heappush(heap,(ke+nt,nx))

            elif not (ks<=t<ke) and t+nt < visit[nx]:
                visit[nx] = t+nt
                hq.heappush(heap,(t+nt,nx))

        else:
            if t+nt < visit[nx]:
                visit[nx] = t+nt
                hq.heappush(heap,(t+nt,nx))

• x에서 연결된 노드 nx로 갈 때 필요한 시간 nt
• (x,nx)로 가는 간선정보가 왕의 이동경로 king에 있으면 왕이 이동한 시간 고려
• 그렇지 않은 경우 그냥 추가

 

---

전체코드

from collections import defaultdict as dd
import heapq as hq
import sys
input = lambda : sys.stdin.readline().rstrip()

node,edge = map(int,input().split())
start,end,diff,path = map(int,input().split())

sequence = list(map(int,input().split()))

costs = dd(dict)
for _ in range(edge):
    a,b,cost = map(int,input().split())
    costs[a][b] = cost
    costs[b][a] = cost

king,t = {},0
for i in range(path-1):
    a,b = sequence[i],sequence[i+1]
    nt = costs[a][b]
    king[(a,b)] = (t,t+nt)
    king[(b,a)] = (t,t+nt)
    t += nt

inf = 1e9
visit = [inf]*(node+1)
visit[start] = diff

heap = [(diff,start)]
while heap:

    t,x = hq.heappop(heap)

    if x == end:
        print(t-diff)
        break

    for nx,nt in costs[x].items():

        if (x,nx) in king:
            ks,ke = king[(x,nx)]

            if ks<=t<ke and ke+nt < visit[nx]:
                visit[nx] = ke+nt
                hq.heappush(heap,(ke+nt,nx))

            elif not (ks<=t<ke) and t+nt < visit[nx]:
                visit[nx] = t+nt
                hq.heappush(heap,(t+nt,nx))

        else:
            if t+nt < visit[nx]:
                visit[nx] = t+nt
                hq.heappush(heap,(t+nt,nx))

 

코멘트

푸는거보다 입력이랑 간선 구상하는게 오래걸린듯?

1400 화물차랑 비슷함. 화물차보단 쉬운듯

화물차는 2차원 격자버전, 얘는 그냥 graph 버전