[ 백준 1826 ] 연료 채우기 - Python

문제 보기

이 문제는 그리디(다익스트라) 문제이다.

 

주유소에서 멈추는 횟수를 최소화하는 문제이다.

현재 위치에서 갈 수 있는 곳 중 연료의 양이 가장 많은 곳을 방문하면 된다. 즉 그리디 방식으로 풀면 된다.

 

그리디 방식으로 정답을 구하는 것 자체는 어렵지 않았지만 제한 시간을 고려하면서 구현하기는 어려웠다.

시간제한을 해결하기 위해 현재 위치에서 갈 수 있는 곳은 우선순위 큐에 (-비용, 거리) 형태로 우선순위 큐에 삽입하였고, 갈 수 없는 곳은 (거리, -비용) 형태로 삽입하였다.

 

즉 갈 수 있는 곳은 비용 내림차순으로 정렬된 우선순위 큐이며, 갈 수 없는 곳은 거리 오름차순으로 정렬된 우선순위 큐 형태이다. 갈 수 없는 곳을 (-비용, 거리) 순으로 삽입하면 비용이 높은 곳부터 탐색하지만 (거리, -비용) 형태로 삽입하면 현재 거리에 도달하지 못하는 순간 바로 break를 통해 반복문을 빠져나가면서 시간 초과를 해결할 수 있다.

 

큐를 완성한 후 갈 수 있는 곳에서 하나를 꺼내서 현재 값을 업데이트하고, 업데이트 한 값을 가지고 갈 수 없는 곳에서 다시 갈 수 있는 곳으로 바뀐 곳을 가져온다.

 

더 이상 이동할 수 없거나, 이동을 완료할 때까지 반복하면 된다.

 

코드

import heapq

if __name__ == "__main__":
    n = int(input())  # 주유소의 개수
    q = []
    for _ in range(n):
        distance, cost = map(int, input().split())
        heapq.heappush(q, (-cost, distance))
    l, p = map(int, input().split())  # 마을까지의 거리, 원래 있던 연료의 양

    if p >= l:
        print(0)
    else:
        # 이동 시작
        cnt = 0
        location = 0  # 현재 위치
        sub_q = []
        temp = []
        while True:
            # 갈 수 있는 거리에 있는 위치 찾기
            while q:
                cost, distance = heapq.heappop(q)
                if distance <= location + p:
                    heapq.heappush(sub_q, (cost, distance))
                else:  # 갈 수 없으면
                    heapq.heappush(temp, (distance, cost))

            if len(sub_q) == 0:  # 갈 수 있는 곳이 없는 상황
                break

            # 갈 수 있는 곳에서 제일 연료량이 높은 것 출력
            cost, distance = heapq.heappop(sub_q)
            cost = -cost
            if location < distance:  # 더 먼 곳이면
                p = p - (distance - location) + cost
                location = distance  # 위치 업데이트
            else:
                p += cost  # 비용만 업데이트
            cnt += 1

            if location + p >= l:  # 갈 수 있다면
                print(cnt)
                exit()

            q.extend(sub_q)  # sub_q -> q

            # temp 중에 갈 수 있는거 q로 옮기기
            while temp:
                distance, cost = heapq.heappop(temp)
                if distance <= location + p:
                    heapq.heappush(q, (cost, distance))
                else:
                    heapq.heappush(temp, (distance, cost))
                    break
            sub_q = []

        # 갈 수 없는 경우
        print(-1)