[algospot] TICTACTOE

문제링크 입니다

댓글에 char 캐스팅 하는거 안알려줬으면 못 풀뻔 했네요 ㅜㅜ. 어지럽다….

[TICTACTOE] 문제 😂😂😂😂😂

틱택토는 3x3 크기의 게임판에서 하는 3목 게임입니다. 두 명이 번갈아가며 o와 x를 게임판의 빈 칸에 쓰되, 먼저 같은 글자를 가로, 세로 혹은 대각선으로 3개 쓰이도록 하는 쪽이 이깁니다.

틱택토 게임판의 현재 상태가 주어집니다. 두 사람 모두 최선을 다한다고 가정할 때, 어느쪽이 이길지 판단하는 프로그램을 작성하세요.

입력

입력의 첫 줄에는 테스트 케이스의 수 C(<= 50)가 주어집니다. 각 테스트 케이스는 세 줄에 각 세 글자로 게임판의 각 위치에 쓰인 글자가 주어집니다. 글자가 없는 칸은 마침표(.)로 표현합니다.

출력

각 테스트 케이스마다 한 줄을 출력합니다. 두 사람이 모두 최선을 다할 경우 비긴다면 TIE를, 아닌 경우 이기는 사람의 글자를 출력합니다.

입력 예제

3
...
...
...
xx.
oo.
...
xox
oo.
x.x

출력 예제

TIE
x
o

전체 코드는 다음과 같습니다.

//
//  TICTACTOE.cpp
//  AALGGO
//
//  Created by inhyeok on 2021/10/14.
//


#include <iostream>
#include <fstream>
#include <string> // string
#include <vector>
using namespace std;

ifstream fin("TICTACTOE.txt");

//cache 를 -2 로 리셋
// 3^9 = 19683;
int cache[19683];

void preCalc(){
    for(int i=0; i<19683 ; i++){
        cache[i] = -2;
    }
}

//turn 이 한줄을 만들었는지 판단한다.
bool isFinished(const vector<string>& board, char turn){
    // 가로중에 세개가 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;
    }
    // 대각선 1시에서 7시
    if(board[0][0] == turn && board[1][1] == turn && board[2][2] == turn) return true;
    // 대각서 11시에서 5시
    if(board[0][2] == turn && board[1][1] == turn && board[2][0] == turn) return true;

    return false;
}


// 틱택토 게임판이 주어질 때 [0, 19682] 범위의 정수로 변환한다.
int bijection(const vector<string>& board){
    int ret =0;
    for(int i=0; i< 3; i++){
        for(int j=0; j<3; j++){
            ret = ret * 3;
            if(board[i][j] == 'o') ret++;
            else if(board[i][j] == 'x') ret += 2;
        }
    }
    return ret;
}

// 이기면 1 비기면 0 지면 -1
int canWin(vector<string>& board, char turn){
    //기저 사례 다음턴이 이기면 짐
    if(isFinished(board, 'o'+'x'-turn)) return -1;
    int &ret = cache[bijection(board)];
    if(ret!=-2) return ret;
    // 모든 반환값의 미니멈 -2
    int minValue = 2;
    // 보드판에 비어있을때.
    for(int y=0; y<3; y++){
        for(int x=0; x<3; x++){
            if(board[y][x] == '.'){
                board[y][x] = turn;
                minValue = min(minValue, canWin(board,'o'+'x'-turn)); // 다음턴에 상대가 이기든지 지든지.
                board[y][x] = '.';
            }
        }
    }
    // 더이상 플레이 할 수 없거나 지는것이 최선일 경우
    if(minValue==2 || minValue==0) return ret = 0;
    // 최선이 상대가 이기는 거라면 난 무조건 지고, 상대가 지는 거라면 난 이긴다.
    return ret = -minValue;
}


int main(int argc, const char * argv[]) {
    int test_case;
    fin >> test_case;
    vector<string> board;
    for(int i = 0; i < test_case; i++){
        board.clear();
        int checkturn = 0;
        for(int j=0; j< 3; j++){
            string temp;
            fin >> temp;
            for(int k=0; k<3; k++){
                if(temp[k] != '.') checkturn++;
            }
            board.push_back(temp);
        }
        char turn = 'x';
        if( checkturn % 2 == 1) turn = 'o';
        preCalc(); // -2로 캐시 초기화
        int result = canWin(board, turn);
        switch(result){
            case -1: // 지면
                cout << (char)('o'+'x'-turn) << endl;
                break;
            case 0: // 비기면
                cout << "TIE" << endl;
                break;
            case 1: // 이기면
                cout << turn << endl;
                break;
        }

    }
    return 0;
}