algospot :: TICTACTOE 틱택토

알고리즘 문제해결전략 책을 바탕으로 코드를 작성함

 1) 캐시

 3*3 보드이고, 각 칸에는 x, o, . 3가지 케이스가 있으므로 이를 9자리의 3진수 정수로 표현할 수 있음. => int cache[MAX];

보드판을 받아서 그에 대응하는  9자리의 3진수 정수로 변환해주는 함수(int bijection()) 를 활용하여 캐시를 채워줌.

 캐시에는 현재 보드판에서 다음 턴(x 또는 o) 사람의 최선이 이기는것, 지는것, 비기는 것 중 어느것인지를 저장.

 

 2) 재귀함수

보드판에서 이번에 둘 사람에게 일어날 수 있는 최대를 저장한다고 하자. 

예를들어 이번에 어디에 두느냐에 따라 이길수도, 질수도, 비길수도 있다면 '이긴다'를 저장하고

지거나 비긴다면 '비긴다'를

질수밖에 없다면 '진다'를 저장한다.

이긴다는 1, 비긴다는 0, 진다는 -1로 저장한다.

위의 그림과 같이 나는 이번 턴에 상대방의 상황을 최악으로 하는 수를 두어야 하므로, 놓을 수 있는 모든 자리 중 다음 턴에 상대방의 상황을 최악으로 하는, -1, 0, 1   중 minimum인 수를 선택한다.

#include <iostream>
#include <vector>
#define MAX 19683
#define FOR(var, num) for(int var = 0 ; var < num; var++)

using namespace std;
int cache[MAX];
vector<string> board;

bool printBoard(){
    FOR(line, 3)
    cout << board[line] << endl;
}

// turn이 이미 한줄을 만들었는지 확인. 만들었다면 true 반환
bool isFinished( char turn){
    //가로 줄 확인
    FOR(line, 3){
        FOR(col, 3){
            if(board[line][col] != turn) break;
            if(col == 2) return true;
        }
    }
    // 세로 줄 확인
    FOR(col, 3){
        FOR(row, 3){
            if(board[row][col] != turn) break;
            if(row == 2) return true;
        }
    }
    // 대각선 왼쪽아래
    FOR(line, 3){
        if(board[line][line] != turn) break;
        if(line == 2) return true;
    }
    // 대각선 오른쪽 아래
    FOR(line, 3){
        if(board[line][2-line] != turn) break;
        if(line == 2) return true;
    }
    return false;
}
//3*3 보드판을 9자리 3진수로 변환 
int bijection(){
    int ret = 0;
    FOR(row, 3){
        FOR(col, 3){
            ret *= 3;
            if(board[row][col] == 'x') ret++;
            else if (board[row][col] =='o') ret+=2;
        }
    }
    return ret;
}
int tictactoe(char thisTurn){
    //저번 턴에 상대가 벌써 한 줄을 만들었다면 게임은 내가 지는 것으로 마무리 됨
    if(isFinished('x'+'o'-thisTurn)){
        return -1; // thisTurn 이 진다
    }
    
    int& cacheRef = cache[bijection()];
    if(cacheRef != -2) return cacheRef;
    //빈 자리에 말을 두면서 동적 프로그래밍으로 이번 턴에서 최대의 결과를 찾음.
    int minVal = 2;
    FOR(row, 3){
        FOR(col, 3){
            if(board[row][col]=='.'){
                if(minVal == -1) break;
                board[row][col] = thisTurn;
                minVal = min(minVal,tictactoe('x'+'o'-thisTurn));
                board[row][col] = '.';
            }
        }
    }
    if(minVal == 2) return cacheRef = 0;
    return cacheRef = -minVal;

}
int main(){
//    freopen("input.txt", "r", stdin);
    int tc;
    cin >> tc;
    FOR(i, MAX){
        cache[i] = -2;
    }
    while(tc --){
        board.clear();
        int init_count = 0;
        char init_char = 'x';

        //input
        FOR(line, 3){
            string input;
            cin >> input;
            FOR(cha, 3)
                if(input[cha]!='.') init_count ++;
            board.push_back(input);
        }
        if(init_count%2 == 1) init_char = 'o';

        int result = tictactoe(init_char);

        if(result == 1) cout << init_char << endl;
        else if(result == -1){
            char opp = 'x'+'o'-init_char;
            cout << opp << endl;
        }
        else cout <<"TIE" <<endl;

    }
}