샘플 문제 : TIC-TAE-TOE

📌 1. 문제 정의 - 무엇을 풀 것인가?

Tic-Tac-Toe(틱택토)는 다음과 같은 규칙을 가진 게임입니다:

• 두 명의 플레이어가 번갈아 가며 O, X를 3x3 보드에 놓습니다.
• 가로, 세로, 대각선 중 한 줄을 같은 문자로 먼저 채우면 승리합니다.
• 보드가 가득 찰 때까지 승자가 없다면 무승부입니다.

✅ 이번 문제의 목적

현재 주어진 보드 상태에서 현재 플레이어가 이길 수 있는지, 질지, 무승부일지를 미리 예측하는 알고리즘을 구현합니다.

---

🧠 2. 핵심 전략 - 동적 계획법(DP)으로 탐색 최적화

틱택토는 최대 9개의 칸에 O, X, .(빈칸) 중 하나가 들어갈 수 있습니다.

• 가능한 모든 상태의 수 = (3^9 = 19683)
• 모든 상태에 대한 결과를 미리 계산하고 저장(caching)하여 중복 계산을 방지합니다.

---

🧩 3. 게임 상태 모델링

enum
{
    DEFAULT = 2, // 계산 전 상태
    WIN = 1,     // 현재 플레이어가 이김
    DRAW = 0,    // 무승부
    LOSE = -1    // 현재 플레이어가 짐
};

• DEFAULT: 아직 계산되지 않은 상태
• WIN / DRAW / LOSE: 현재 플레이어 기준의 게임 결과

---

🔐 4. 보드 상태를 해싱하여 캐시 키로 사용하기

int HashKey(const vector<vector<char>>& board)
{
    int ret = 0;
    for (int y = 0; y < 3; y++)
    {
        for (int x = 0; x < 3; x++)
        {
            ret = ret * 3;
            if (board[y][x] == 'o') ret += 1;
            else if (board[y][x] == 'x') ret += 2;
        }
    }
    return ret;
}

🔍 작동 방식:

• 보드를 3진법으로 변환
  • '.' = 0, 'o' = 1, 'x' = 2
• 총 9칸 → (3^9 = 19683) 개의 상태를 int로 표현 가능
• 해당 숫자를 캐시의 인덱스로 사용

---

🏁 5. 승리 조건 판별 함수

bool IsFinished(const vector<vector<char>>& board, char turn)
{
    for (int i = 0; i < 3; i++)
        if (board[i][0] == turn && board[i][1] == turn && board[i][2] == turn)
            return true;

    for (int i = 0; i < 3; i++)
        if (board[0][i] == turn && board[1][i] == turn && board[2][i] == turn)
            return true;

    if (board[0][0] == turn && board[1][1] == turn && board[2][2] == turn)
        return true;

    if (board[0][2] == turn && board[1][1] == turn && board[2][0] == turn)
        return true;

    return false;
}

• 가로 / 세로 / 대각선 3줄을 순회하며 모두 turn이면 승리

---

🧮 6. 핵심 함수: 승패 판단 CanWin()

int CanWin(vector<vector<char>>& board, char turn)
{
    // 1. 기저 사례: 상대가 이긴 경우 → 나의 패배
    if (IsFinished(board, 'o' + 'x' - turn))
        return LOSE;

    // 2. 캐시 확인
    int key = HashKey(board);
    int& ret = cache[key];
    if (ret != DEFAULT)
        return ret;

    // 3. 가능한 모든 착수 시도
    int minValue = DEFAULT;
    for (int y = 0; y < 3; y++)
    {
        for (int x = 0; x < 3; x++)
        {
            if (board[y][x] != '.') continue;

            board[y][x] = turn;  // 착수
            minValue = min(minValue, CanWin(board, 'o' + 'x' - turn)); // 상대 차례
            board[y][x] = '.';   // 복원
        }
    }

    // 4. 결과 정리
    if (minValue == DRAW || minValue == DEFAULT)
        return ret = DRAW;

    return ret = -minValue;
}

📌 핵심 로직 요약

• minValue는 상대방 기준 최선의 결과
• 내가 이기려면 → 상대가 지게 만들어야 함
• -minValue를 리턴해서 나의 결과로 전환

---

🚀 7. 전체 실행 예시 (main() 함수)

int main()
{
    board = {
        {'o', 'x', 'x'},
        {'.', 'o', '.'},
        {'o', '.', '.'}
    };

    for (int i = 0; i < 19683; i++)
        cache[i] = DEFAULT;

    int result = CanWin(board, 'x');

    switch (result)
    {
    case WIN:  cout << "Win" << endl; break;
    case DRAW: cout << "Draw" << endl; break;
    case LOSE: cout << "Lose" << endl; break;
    }
}

✅ 출력 예시

보드 상태:

o x x
. o .
o . .

• X의 차례
• 결과: Win → 현재 X가 반드시 이길 수 있는 경로 존재

---

📌 8. 주의 사항: 캐시 초기화 시 memset 주의

// int형 배열에 memset으로 -1 사용 가능
memset(cache, -1, sizeof(cache)); // -1은 0xFFFFFFFF → 가능

// 하지만 -2는 안 됨! (1바이트로는 표현 불가)

---