[파이썬/python] 백준 - 20007 떡 돌리기

문제

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

---

문제 설명

1. 성현이는 이웃집에 떡을 돌린다.
2. 떡은 한번에 하나씩만 들고 갈 수 있다.
3. 집들 사이에는 총 M개의 양방향 도로가 존재한다.
   1. 성현이는 하루에 X보다 먼 거리를 걷지 않고 거리가 가까운 집부터 방문한다.
   2. 잠은 꼭 본인 집에서 자야 하므로 왕복 불가한 거리는 다음날에 간다.
4. 모든 집에 떡을 돌리기 위해 최소 며칠이 소요되는지 구한다.

 

---

풀이

최단 거리 탐색 알고리즘을 통해 풀어야 하는 문제이다. 이 때 각 도로마다 거리가 다르다. 즉 가중치가 모두 다른 최단 거리 탐색이기 때문에, 다익스트라 알고리즘을 통해 최단거리를 탐색했다.

 

하지만 이 문제는 최단거리를 탐색하는 것이 문제가 아니다. X를 넘지 않으면서, 최소 몇 일 안에 모든 집을 방문할 수 있는가를 구해야 한다.

 

따라서 다익스트라로 갱신한 최단 거리를 오름차순으로 정렬한 후, 낮은 거리부터 왕복거리를 더해가며 X를 초과할 때 마다 Day를 1씩 늘려가며, 최소 며칠이 필요한지 구했다.

 

다익스트라 알고리즘에 익숙하다면, 어렵지 않게 풀 수 있는 문제였다.

 

1. 다익스트라 알고리즘을 통해 각 노드 별 최단 거리를 갱신한다.
2. 최단 거리를 오름차순으로 정렬한다. (거리가 가까운 집 부터 방문하기 때문에)
3. 각 집의 왕복거리를 순차적으로 더하며, X를 넘을 때마다 1일을 더한다.
4. 최소 일을 출력한다.

---

코드

import sys
import heapq
input = sys.stdin.readline
INF = sys.maxsize

n,m,x,y = map(int,input().split())
dist = [INF for _ in range(n)]
dist[y] = 0
hq = [(0,y)]
heapq.heapify(hq)
graph = [[] for _ in range(n)]

def dijkstra():
    while hq:
        cur_cost,v1 = heapq.heappop(hq)
        if dist[v1] < cur_cost:
            continue
        for v2,cost in graph[v1]:
            if cur_cost + cost < dist[v2]:
                dist[v2] = cur_cost + cost
                heapq.heappush(hq,(cur_cost + cost, v2))

for _ in  range(m):
    v1,v2,cost = map(int,input().split())
    graph[v1].append((v2,cost))
    graph[v2].append((v1,cost))
dijkstra()
dist.sort()
total = 0
day = 0
for d in dist:
    if d*2 > x:
        print(-1)
        exit()
    if total + d*2 > x:
        day += 1
        total = d*2
    else:
        total += d*2
if total:
    day += 1
print(day)

---

시간복잡도

• 우선순위 큐를 사용했으므로 다익스트라의 시간복잡도는 $ElogV$이다.
• 최악의 경우 $V = 10^3, E = 10^5$이므로 약 $O(10^6)$의 시간복잡도가 소요된다.