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

C++로 푸는 24 게임(24 Game): 백트래킹 완전 탐색 알고리즘

문제 개요

네 장의 카드가 있고, 각 카드에는 1부터 9 사이의 숫자가 적혀 있다고 가정해 보겠습니다. 목표는 이 숫자들에 +, -, *, / 연산자를 적절히 조합해 최종 결과가 정확히 24가 되는지 판별하는 것입니다.

예를 들어 [4, 9, 2, 6]이 주어졌다면 다음과 같이 계산할 수 있습니다.

(4 × 9) − (2 × 6) = 36 − 12 = 24

따라서 이 경우 정답은 true입니다.

접근 방법: 재귀와 백트래킹

이 문제는 가능한 모든 조합을 시도하는 완전 탐색 방식으로 해결할 수 있습니다. 핵심 아이디어는 다음과 같습니다.

  • 두 장의 카드를 골라 하나의 연산자로 계산하고, 그 결과를 새로운 숫자로 대체합니다.
  • 연산이 한 번 일어날 때마다 카드 수가 하나씩 줄어듭니다.
  • 카드가 한 장만 남으면 그 값이 24인지 검사합니다.
  • 실패하면 이전 상태로 되돌아가(백트래킹) 다른 숫자 쌍과 연산자를 시도합니다.

나눗셈 과정에서 실수가 발생할 수 있으므로, 24와 비교할 때는 오차 허용 범위 epsilon = 10^-5를 사용합니다. 즉, 계산 결과가 24와의 차이가 0.00001 이하이면 성공으로 판정합니다.

알고리즘 단계

  1. 오차 허용 범위를 epsilon := 10^-5로 설정합니다.
  2. 배열 v를 매개변수로 받는 solve() 함수를 정의합니다.
  3. v의 크기가 1이면, |v[0] − 24.0| ≤ epsilon일 때 true를 반환합니다.
  4. 이중 반복문으로 서로 다른 두 인덱스 i, j를 선택합니다(i == j인 경우는 건너뜁니다).
  5. i와 j를 제외한 나머지 숫자들을 담는 새 배열 res를 만듭니다.
  6. 네 가지 연산자(+, -, *, /)를 차례로 적용한 결과 v[i] op v[j]를 res에 추가합니다.
  7. solve(res)를 재귀 호출해 true가 나오면 즉시 true를 반환합니다.
  8. false라면 res의 마지막 원소를 제거해(백트래킹) 다른 연산자를 시도합니다.
  9. 모든 경우를 시도해도 실패하면 false를 반환합니다.

메인 함수에서는 입력 배열 nums의 값을 double형 벡터 v에 옮긴 뒤 solve(v)를 호출해 결과를 얻습니다.

C++ 구현 코드

#include <bits/stdc++.h>
using namespace std;
class Solution {
public:
    char operators[4] = {'+', '-', '/', '*'};
    double epsilon = pow(10.0, -5);
    bool judgePoint24(vector<int>& nums) {
        vector <double> v;
        for(int i = 0; i < nums.size(); i++){
            v.push_back(nums[i]);
        }
        return solve(v);
    }
    bool solve(vector <double> v){
        if(v.size() == 1){
            return abs(v[0] - 24.0) <= epsilon;
        }
        for(int i = 0; i < v.size(); i++){
            for(int j = 0; j < v.size(); j++){
                if(i == j) continue;
                vector <double> res;
                for(int k = 0; k < v.size(); k++){
                    if(i != k && j != k){
                        res.push_back(v[k]);
                    }
                }
                for(int k = 0; k < 4; k++){
                    if(operators[k] == '+'){
                        res.push_back(v[i] + v[j]);
                    }else if(operators[k] == '-'){
                        res.push_back(v[i] - v[j]);
                    }else if(operators[k] == '*'){
                        res.push_back(v[i] * v[j]);
                    }else{
                        res.push_back(v[i] / v[j]);
                    }
                    if(solve(res)) return true;
                    res.pop_back();
                }
            }
        }
        return false;
    }
};
int main(){
    Solution ob;
    vector<int> v = {4,9,2,6};
    cout << (ob.judgePoint24(v));
}

입력

{4,9,2,6}

출력

1

정리

출력이 1(true)이므로 [4, 9, 2, 6]으로 24를 만들 수 있음을 확인했습니다. 이 풀이는 매 단계에서 순서쌍 선택(최대 4×3가지)과 연산자 선택(4가지)을 재귀적으로 반복하므로, 카드가 4장일 때 전체 탐색 횟수는 약 9,000회 수준으로 충분히 빠르게 동작합니다. 부동소수점 오차를 epsilon으로 처리한다는 점만 기억하면, 백트래킹 기반 완전 탐색으로 깔끔하게 해결되는 대표적인 알고리즘 문제입니다.