문제 정의
원 위에 n개의 주유소가 배치되어 있고, 각 주유소에 대해 다음 두 가지 정보가 주어진다고 가정해 봅시다.
- 각 주유소가 보유하고 있는 기름의 양
- 현재 주유소에서 다음 주유소까지의 거리
목표는 트럭이 모든 주유소를 지나며 원을 한 바퀴 완주할 수 있는 최초의 출발 지점을 구하는 것입니다. 단, 트럭은 기름 1리터로 거리 1단위를 이동할 수 있다고 가정합니다.
예를 들어 4개의 주유소가 있고, 각 주유소의 (기름 양, 다음 주유소까지의 거리)가 [(4, 6), (6, 5), (7, 3), (4, 5)]라고 합시다. 이 경우 트럭이 원형 투어를 성공적으로 마칠 수 있는 시작 지점은 2번째 주유소이며, 출력값은 start = 1(두 번째 주유소의 인덱스)이 되어야 합니다.
풀이 접근 방법: 큐(Queue) 활용
이 문제는 큐 자료구조를 사용하면 효율적으로 해결할 수 있습니다. 큐에는 현재 진행 중인 투어 경로가 저장되며, 동작 과정은 다음과 같습니다.
- 첫 번째 주유소를 큐에 삽입하는 것으로 시작합니다.
- 투어가 완성되거나 현재 남은 기름량이 음수가 될 때까지 주유소를 계속해서 큐에 추가합니다.
- 기름량이 음수가 되면 큐가 빌 때까지 앞쪽 주유소부터 하나씩 제거하면서 새로운 시작 후보를 탐색합니다.
이 방식은 각 주유소가 최대 한 번씩만 삽입·삭제되므로 전체 시간 복잡도는 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
마무리
위 알고리즘은 큐를 활용해 실패한 시작 지점을 건너뛰며 탐색 범위를 줄이기 때문에, 모든 시작점을 일일이 검사하는 브루트 포스 방식(O(n²))보다 훨씬 효율적입니다. 만약 어떤 시작 지점으로도 원을 완주할 수 없다면 함수는 -1을 반환하여 해답이 존재하지 않음을 알려줍니다.