C++ 그리디 알고리즘으로 푸는 최소 급유 정지 횟수 문제

문제 개요

자동차가 출발 지점에서 동쪽으로 t마일 떨어진 목적지까지 이동하는 상황을 생각해 봅시다.

이동 경로에는 여러 개의 주유소가 있습니다. 각 station[i]은 출발점에서 동쪽으로 station[i][0]마일 떨어진 위치에 있는 주유소를 나타내며, 해당 주유소에는 station[i][1]리터의 연료가 저장되어 있습니다.

자동차는 무한대 크기의 연료 탱크를 갖고 있으며, 출발 시 startFuel리터의 연료가 들어 있습니다. 자동차는 1마일 주행할 때마다 1리터의 연료를 소모합니다.

자동차가 주유소에 도착하면 잠시 멈춰 주유할 수 있으며, 이때 주유소에 있는 모든 연료를 차량 탱크로 옮겨 담게 됩니다. 목표는 목적지에 도달하기 위해 필요한 최소 급유 정지 횟수를 구하는 것이며, 목적지에 도달하는 것이 불가능한 경우 -1을 반환해야 합니다.

예시로 이해하기

입력이 다음과 같다고 가정해 보겠습니다.

Target = 100, startFuel = 10, stations = [[10,40],[20,30],[30,20],[60,40]]

이때 출력은 3이 됩니다. 과정을 단계별로 살펴보면 다음과 같습니다.

처음 10리터의 연료로 첫 번째 주유소가 있는 10마일 지점까지 이동할 수 있습니다.
첫 번째 주유소에서 40리터를 주유받으면 총 50리터가 되어 50마일 지점까지 갈 수 있습니다.
도달 가능한 범위 안에 있는 두 번째(20마일, 30리터)와 세 번째(30마일, 20리터) 주유소 중 더 많은 연료를 제공하는 곳에서 30리터를 주유받으면 총 80리터가 되어 80마일 지점까지 이동할 수 있습니다.
네 번째 주유소(60마일)에서 40리터를 주유받으면 총 120리터가 되어 목적지인 100마일 지점에 충분히 도달할 수 있습니다.

따라서 필요한 급유 정지 횟수는 3회입니다.

해결 접근 방법

이 문제는 그리디(Greedy) 알고리즘과 우선순위 큐(Priority Queue)를 활용하면 효율적으로 해결할 수 있습니다. 핵심 아이디어는 다음과 같습니다.

현재 연료로 도달 가능한 범위 내에 있는 모든 주유소의 연료 양을 우선순위 큐에 넣어두고, 연료가 부족해질 때마다 큐에서 가장 많은 연료를 제공하는 주유소를 꺼내 주유하는 것입니다. 이렇게 하면 불필요한 정지를 최소화할 수 있습니다.

구체적인 알고리즘 단계는 다음과 같습니다.

curr := 0으로 초기화합니다.
배열 st를 정렬합니다.
우선순위 큐 pq를 정의합니다.
i := 0, cnt := 0으로 초기화합니다.
curr := curr + fuel로 설정합니다.
curr < target인 동안 다음을 반복합니다.
- cnt를 1 증가시킵니다.
- i < st의 크기이면서 st[i][0] <= curr인 동안 st[i][1]을 pq에 삽입하고 i를 1 증가시킵니다.
- pq가 비어 있다면 루프를 종료합니다.
- curr := curr + pq의 최상위 원소로 갱신합니다.
- pq에서 원소를 삭제합니다.
curr >= target이면 cnt를, 그렇지 않으면 -1을 반환합니다.

C++ 구현 예제

아래 구현 예제를 통해 더 잘 이해해 보겠습니다.

#include <bits/stdc++.h>
using namespace std;
class Solution {
    public:
    int minRefuelStops(int target, int fuel, vector<vector<int>> &st) {
        int curr = 0;
        sort(st.begin(), st.end());
        priority_queue<int> pq;
        int i = 0;
        int cnt = 0;
        curr += fuel;
        while (curr < target) {
            cnt++;
            while (i < st.size() && st[i][0] <= curr) {
                pq.push(st[i][1]);
                i++;
            }
            if (pq.empty())
                break;
            curr += pq.top();
            pq.pop();
        }
        return curr >= target ? cnt : -1;
    }
};
main(){
    Solution ob;
    vector<vector<int>> v = {{10,40},{20,30},{30,20},{60,40}};
    cout << (ob.minRefuelStops(100, 10, v));
}

입력

100, 10, {{10,40},{20,30},{30,20},{60,40}}