원 위에 n개의 주유소(petrol pump)가 있다고 가정해 봅시다. 각 주유소마다 다음 두 가지 정보가 주어집니다.
- 각 주유소에 저장된 휘발유(연료)의 양
- 한 주유소에서 다음 주유소까지의 거리
이때 트럭이 원을 한 바퀴 완주할 수 있는 최초의 출발 지점을 구하는 것이 이 문제의 목표입니다. 단, 트럭은 1리터의 연료로 1단위 거리를 이동할 수 있다고 가정합니다.
문제 예시
예를 들어 4개의 주유소가 있고, 각각의 (연료량, 다음 주유소까지의 거리)가 아래와 같이 주어졌다고 합시다.
- (4, 6), (6, 5), (7, 3), (4, 5)
이 경우 트럭이 원을 완주할 수 있는 첫 번째 출발 지점은 두 번째 주유소입니다. 따라서 출력 결과는 start = 1(0부터 시작하는 인덱스 기준)이 되어야 합니다.
접근 방법: 큐(Queue) 활용
이 문제는 큐(queue)를 사용하면 효율적으로 해결할 수 있습니다. 큐에는 현재 진행 중인 순환 경로(tour)를 저장하며, 알고리즘은 다음과 같이 동작합니다.
- 첫 번째 주유소를 큐에 삽입하고, 순환이 완료되거나 현재 남은 연료량이 음수가 될 때까지 주유소를 계속 추가합니다.
- 남은 연료량이 음수가 되면 큐가 빌 때까지 앞쪽 주유소부터 제거하고, 새로운 시작 지점에서 다시 시도합니다.
이 방식은 모든 주유소를 최대 한 번씩만 삽입/삭제하므로 전체 시간 복잡도는 O(n)으로 매우 효율적입니다.
C++ 구현 예제
#include <iostream>
using namespace std;
class pump {
public:
int petrol;
int distance;
};
int findStartIndex(pump pumpQueue[], int n) {
int start_point = 0;
int end_point = 1;
int curr_petrol = pumpQueue[start_point].petrol - pumpQueue[start_point].distance;
while (end_point != start_point || curr_petrol < 0) {
while (curr_petrol < 0 && start_point != end_point) {
curr_petrol -= pumpQueue[start_point].petrol - pumpQueue[start_point].distance;
start_point = (start_point + 1) % n;
if (start_point == 0)
return -1;
}
curr_petrol += pumpQueue[end_point].petrol - pumpQueue[end_point].distance;
end_point = (end_point + 1) % n;
}
return start_point;
}
int main() {
pump PumpArray[] = {{4, 6}, {6, 5}, {7, 3}, {4, 5}};
int n = sizeof(PumpArray)/sizeof(PumpArray[0]);
int start = findStartIndex(PumpArray, n);
if(start == -1)
cout<<"No solution";
else
cout<<"Index of first petrol pump : "<<start;
}실행 결과
Index of first petrol pump : 1
동작 설명
start_point는 현재 순환 경로의 시작 후보 지점을,end_point는 다음으로 탐색할 주유소를 가리킵니다.curr_petrol은 현재까지 누적된 남은 연료량으로, 각 주유소에서 (연료량 − 거리) 값을 더하거나 빼며 갱신됩니다.- 누적 연료량이 음수가 되면 해당 시작 지점에서는 완주가 불가능하므로 시작 지점을 뒤로 옮기고, 그 지점의 연료 차액을 다시 환원합니다.
start_point가 다시 처음(0)으로 돌아가면 더 이상 가능한 시작 지점이 없다는 의미이므로 -1을 반환합니다.
만약 어떠한 시작 지점에서도 원을 완주할 수 없다면 함수는 -1을 반환하고, 프로그램은 "No solution"을 출력합니다.