문제 개요
두 명의 플레이어가 번갈아 가며 진행하는 뒤집기 게임(Flip Game)을 생각해 보겠습니다. 주어진 문자열에는 오직 두 가지 문자, 즉 +와 -만 포함되어 있습니다. 플레이어 1과 플레이어 2는 자신의 차례에 연속된 두 개의 "++"를 "--"로 뒤집어야 합니다. 더 이상 뒤집을 수 있는 위치가 없는 플레이어가 등장하면 게임이 종료되며, 그 시점에 마지막으로 수를 둔 상대편이 승리하게 됩니다.
우리가 구현해야 할 함수는 선공 플레이어가 최선의 전략으로 플레이할 때 반드시 승리를 보장할 수 있는지를 판별하는 것입니다.
예를 들어 입력이 s = "++++"라고 해봅시다. 이 경우 출력은 true입니다. 선공 플레이어가 가운데의 "++"를 뒤집어 "+--+"로 만들면, 상대는 어떤 수를 두더라도 결국 지게 되기 때문입니다.
풀이 접근 방법
이 문제는 재귀 호출과 메모이제이션(Memoization)을 조합하면 효율적으로 해결할 수 있습니다. 핵심 아이디어는 다음과 같습니다. 현재 상태에서 어떤 한 수를 두었을 때 상대방이 그 결과 상태에서 승리할 수 없다면, 현재 플레이어는 그 수를 선택함으로써 승리를 보장할 수 있다는 것입니다.
단계별로 살펴보면 다음과 같습니다.
- 중복 계산을 피하기 위해 메모이제이션용 맵
memo를 하나 정의합니다. - 문자열
s를 인자로 받는 재귀 함수solve()를 정의합니다. s가 이미memo에 저장되어 있다면, 추가 계산 없이memo[s]를 바로 반환합니다.possible을false로 초기화하고, 문자열의 길이를n에 저장합니다.i를 0부터n-2까지 순회하면서 다음 작업을 반복합니다.s[i]와s[i+1]이 모두 '+'라면 두 문자를 임시로 '-'로 변경합니다.possible |= !solve(s)를 통해 상대방이 필패 상태에 빠지는지 확인합니다.- 탐색이 끝나면 문자열을 원래대로 복구('+')하여 백트래킹을 완성합니다.
possible이 참이 되는 순간 곧바로 결과를 저장하고 반환하여 불필요한 탐색을 줄입니다.
- 모든 경우를 확인했는데도 승리 경로가 없다면
false를 반환합니다. - 메인 함수에서는 단순히
solve(s)의 결과를 반환하면 됩니다.
C++ 구현 예제
아래 코드를 통해 실제 동작을 더 잘 이해할 수 있습니다.
#include <bits/stdc++.h>
using namespace std;
class Solution {
public:
unordered_map <string, bool> memo;
bool solve(string s){
if (memo.count(s))
return memo[s];
bool possible = false;
int n = s.size();
for (int i = 0; i < n - 1; i++) {
if (s[i] == '+' && s[i + 1] == '+') {
s[i] = '-';
s[i + 1] = '-';
possible |= !solve(s);
s[i] = '+';
s[i + 1] = '+';
if (possible)
return memo[s] = possible;
}
}
return memo[s] = possible;
}
bool canWin(string s) {
return solve(s);
}
};
main(){
Solution ob;
cout << (ob.canWin("++++"));
}
입력
"++++"
출력
1
복잡도 분석
메모이제이션을 사용하지 않으면 각 상태에서 가능한 모든 뒤집기를 일일이 시도해야 하므로 지수적인 시간 복잡도가 발생합니다. 하지만 게임 도중 동일한 문자열 상태가 반복해서 등장하는 특징이 있기 때문에, 맵을 이용해 한 번 계산한 결과를 캐싱해 두면 중복 탐색이 크게 줄어들고 전체 실행 속도가 눈에 띄게 향상됩니다.