C++로 풀어보는 자동차 경주 문제: BFS로 최단 명령 시퀀스 찾기

무한히 뻗은 수직선 위에서 위치 0에서 출발하여 속도 +1로 달리는 자동차가 있다고 가정해 보겠습니다. 이 자동차는 'A(가속)'와 'R(방향 반전)' 두 가지 명령으로만 구성된 명령 시퀀스에 따라 스스로 움직입니다.

명령 규칙

'A' 명령 (Accelerate, 가속)

position := position + speed (현재 속도만큼 전진)
speed = speed * 2 (속도를 2배로 증가)

'R' 명령 (Reverse, 방향 반전)

속도가 양수라면 speed = -1
그렇지 않다면 speed = 1

예를 들어 명령 "AAR"을 실행하면 자동차의 위치는 0->1->3->3 순서로 이동하고, 속도는 1->2->4->-1 순서로 변화합니다.

문제 정의

목표 지점(target)이 주어졌을 때, 해당 위치에 도달하기 위한 가장 짧은 명령 시퀀스의 길이를 구하는 것이 이 문제의 핵심입니다.

예를 들어 target = 6이 주어진다면, 출력은 5가 됩니다. 가능한 명령 시퀀스 중 하나인 "AAARA"를 실행하면 위치는 0->1->3->7->7->6 순서로 이동하여 목표에 도달하기 때문입니다.

해결 접근 방법: 너비 우선 탐색(BFS)

이 문제는 각 상태(위치, 속도)를 노드로 보고, 'A'와 'R' 명령을 간선으로 취급하는 그래프 탐색 관점에서 접근할 수 있습니다. 최단 길이를 구해야 하므로 BFS(너비 우선 탐색)가 적합합니다. 해결 단계는 다음과 같습니다.

방문 여부를 기록할 집합(set) visited를 정의합니다.
탐색용 큐(queue) q를 정의하고 초기 상태 {0, 1}을 삽입합니다.
level을 0부터 시작하여 큐가 빌 때까지 레벨 단위로 반복합니다.
각 레벨에서 큐에 남아있는 모든 원소를 처리합니다.
- 큐의 맨 앞 원소 curr를 꺼내고, curr의 위치가 target과 같다면 현재 level을 반환합니다.
- 'A' 명령 적용: forward = 위치 + 속도, forwardSpeed = 속도 * 2 로 계산한 뒤, forward > 0이고 |forward - target| < target이며 아직 방문하지 않은 상태라면 큐에 추가합니다.
- 'R' 명령 적용: 현재 위치를 유지하고 속도 부호만 반전한 상태(curr.first, 속도가 양수면 -1, 아니면 1)를 만든 뒤, 같은 조건을 만족하면 큐에 추가합니다.
모든 탐색이 끝나도 도달하지 못하면 -1을 반환합니다.

여기서 |forward - target| < target 조건은 목표에서 너무 멀리 벗어난 상태를 가지치기(pruning)하여 탐색 범위를 줄이는 역할을 하며, 문자열 키("위치*속도")를 사용해 동일한 상태의 중복 방문을 방지합니다.

C++ 구현 예시

#include <bits/stdc++.h>
using namespace std;
class Solution {
public:
   int racecar(int target) {
      unordered_set < string > visited;
      queue < pair <int ,int> > q;
      q.push({0, 1});
      for(int level = 0; !q.empty(); level++){
         for(int k = q.size(); k > 0; k-- ){
            pair <int, int> curr = q.front();
            q.pop();
            if(curr.first == target) return level;
            int forward = curr.first + curr.second;
            int forwardSpeed = curr.second * 2;
            string key = to_string(forward) + "*" + to_string(forwardSpeed);
            if(forward > 0 && abs(forward - target) < target && !visited.count(key)){
               visited.insert(key);
               q.push({forward, forwardSpeed});
            }
            key = to_string(curr.first) + "*" + to_string(curr.second > 0 ? - 1: 1);
            if(curr.first > 0 && abs(target - curr.first) < target && !visited.count(key)){
               visited.insert(key);
               q.push({curr.first, curr.second > 0 ? - 1: 1});
            }
         }
      }
      return -1;
   }
};
main(){
   Solution ob;
   cout << (ob.racecar(6));
}

입력

출력

이처럼 BFS와 상태 가지치기를 결합하면 자동차 경주 문제의 최단 명령 시퀀스 길이를 효율적으로 구할 수 있습니다.