[Python/파이썬] 백준 20007번 떡 돌리기

20007번: 떡 돌리기

 

코드

from heapq import heappop, heappush
import sys
input = sys.stdin.readline

n, m, x, y = map(int, input().split())
roads = [[] for _ in range(n)]
for _ in range(m):
    a, b, c = map(int, input().split())
    roads[a].append((c, b))
    roads[b].append((c, a))

# Dijkstra
dist = [sys.maxsize]*n  # y에서 각 집까지의 최단 거리
dist[y] = 0
q = [(0, y)]

while q:
    d, now = heappop(q)
    for nd, nx in roads[now]:
        if dist[nx] > dist[now]+nd:  # now를 거쳐서 nx로 가는 것이 더 최단 거리인 경우
            heappush(q, (dist[now]+nd, nx))
            dist[nx] = dist[now]+nd

dist.sort()  # 오름차순 정렬
if dist[-1] > x:
    print(-1)
else:
    tmp = 0
    ans = 0
    for d in dist:
        if tmp+d*2 <= x:
            tmp += d*2
        else:
            ans += 1
            tmp = d*2
    print(ans+(1 if tmp > 0 else 0))

 

이 문제에서 주의해야할 점은 떡은 한 번에 하나만 들고 나갈 수 있다는 점이다. 그러므로 한 번 집을 나서서 여러 집에 최대로 떡을 돌리고 오는게 아니고 한 집 배달하고 본인 집 왔다가 다시 배달 가고 이런 식이다. 이 조건을 제대로 안 봐서 처음에 헤맸다.

 

한 번에 떡을 하나씩만 갖고 가고, 거리가 가까운 집부터 방문하므로 이 문제를 풀기 위해서는 성현이의 집에서 각 집까지의 최단 거리를 구하면 된다. 그러므로 한 정점에서 다른 모든 정점까지의 거리를 구하는 알고리즘인 다익스트라를 사용한다. 다익스트라를 사용하여 모든 집까지의 거리를 구한 뒤, 가장 가까운 집부터 방문하며 하루 내로 최대로 배달하고, 다음 날로 넘기고 이 과정을 모든 집에 대해 반복하면 된다.