Computer >> 컴퓨터 >  >> 프로그래밍 >> C++

C++로 풀어보는 주마 게임(Zuma Game) 알고리즘

주마 게임 문제란?

주마 게임(Zuma Game)은 테이블 위에 일렬로 늘어선 공들을 처리하는 흥미로운 알고리즘 문제입니다. 공은 빨강(R), 노랑(Y), 파랑(B), 초록(G), 흰색(W) 다섯 가지 색으로 구성되며, 플레이어 역시 몇 개의 공을 손에 들고 시작합니다.

게임 규칙은 다음과 같습니다. 매 턴마다 손에 든 공 하나를 골라 기존 줄의 원하는 위치에 삽입합니다. 삽입 후 같은 색의 공이 3개 이상 연속으로 붙어 있다면 해당 그룹 전체가 제거됩니다. 이 과정은 더 이상 제거할 수 있는 그룹이 없을 때까지 반복됩니다.

목표는 테이블 위의 모든 공을 없애기 위해 삽입해야 하는 공의 최소 개수를 구하는 것입니다. 만약 어떻게 해도 모든 공을 제거할 수 없다면 -1을 반환해야 합니다.

예제로 이해하기

입력이 "WRRBBW"이고 손에 든 공이 "RBW"라고 가정해 보겠습니다. 이때 정답은 3입니다.

  • RR 뒤에 R을 삽입 → WRR[R]BBW → 제거 후 WBBW
  • BB 뒤에 B를 삽입 → WBB[B]W → 제거 후 WW
  • WW 뒤에 W를 삽입 → WW[W] → 모든 공 제거 완료

총 3개의 공을 사용해 테이블을 비울 수 있습니다.

해결 접근 방식

이 문제는 깊이 우선 탐색(DFS)과 백트래킹을 활용해 해결할 수 있습니다. 핵심 아이디어는 각 연속된 같은 색 그룹에 대해 부족한 개수만큼 공을 채워 넣어 제거를 유발하고, 남은 문자열에 대해 재귀적으로 동일한 과정을 반복하는 것입니다.

1. findMinStep() 함수

  • 문자열 s 끝에 종료 표시용 '#'을 붙입니다.
  • 크기 26의 배열 v를 선언해 손에 든 각 색상별 공의 개수를 카운트합니다.
  • solve(s, v)를 호출한 뒤, 결과가 INF(무한대) 이상이면 -1을, 그렇지 않으면 결과값을 반환합니다.

2. solve() 함수 — 재귀 탐색

  • s가 "#"이면 모든 공이 제거된 것이므로 0을 반환합니다.
  • 두 포인터 i, j를 이용해 연속된 같은 색 그룹의 경계를 찾습니다.
  • need = 3 − (그룹 길이)를 계산해 그룹을 제거하는 데 필요한 공의 개수를 구합니다.
  • 손에 해당 색의 공이 충분히 있다면, 개수를 차감한 상태에서 그룹을 제거한 새 문자열로 재귀 호출하고, 결과의 최솟값을 갱신한 후 백트래킹으로 개수를 복원합니다.

3. process() 함수 — 연쇄 제거

  • 삽입으로 인해 3개 이상 연속된 그룹이 생기면 해당 구간을 문자열에서 삭제합니다.
  • 삭제 후 앞뒤 공이 맞닿으며 새로운 그룹이 형성될 수 있으므로, 포인터를 조정하며 끝까지 검사합니다.

C++ 구현 코드

#include <bits/stdc++.h>
using namespace std;
const int INF = 1e9;
class Solution {
public:
    int findMinStep(string s, string hand) {
        s += "#";
        vector <int> v(26);
        for(int i = 0; i < hand.size(); i++){
            v[hand[i] - 'A']++;
        }
        int ret = solve(s, v);
        return ret >= INF ? -1 : ret;
    }
    int solve(string s, vector <int>& v){
        if(s == "#") return 0;
        int ret = INF;
        for(int i = 0, j = 0; j < s.size(); j++){
            if(s[i] == s[j]) continue;
            int need = 3 - (j - i);
            char x = s[i];
            if(need <= v[x - 'A']){
                v[x - 'A'] -= need;
                ret = min( ret, need + solve(s.substr(0,i) + s.substr(j , s.size() - j), v));
                v[x - 'A'] += need;
            }
            i = j;
        }
        process(s);
        if(s == "#") return 0;
        for(int i = 0, j = 0; j < s.size(); j++){
            if(s[i] == s[j]) continue;
            int need = 3 - (j - i);
            char x = s[i];
            if(need <= v[x - 'A']){
                v[x - 'A'] -= need;
                ret = min( ret, need + solve(s.substr(0,i) + s.substr(j , s.size() - j), v));
                v[x - 'A'] += need;
            }
            i = j;
        }
        return ret;
    }
    void process(string& s){
        for(int i = 0, j = 0; j < s.size(); j++){
            if(s[i] == s[j]) continue;
            if((j - i) >= 3){
                s.erase(i, j - i);
                j = i - 1;
            } else i = j;
        }
    }
};
main(){
    Solution ob;
    cout << (ob.findMinStep("WRRBBW", "RBW"));
}

실행 결과

입력

"WRRBBW", "RBW"

출력

3

마무리

주마 게임 문제는 단순해 보이지만, 삽입 위치와 순서에 따라 연쇄 제거가 발생할 수 있어 모든 경우를 체계적으로 탐색해야 합니다. DFS와 백트래킹을 조합하면 손에 든 공의 개수가 제한적이므로 충분히 효율적인 해법을 구현할 수 있습니다. 특히 종료 조건으로 '#' 센티널 문자를 활용하면 문자열 끝 처리가 한결 깔끔해집니다.