백준, BOJ, 16571번, 알파 틱택토 C++ [CPP] ★★★

이 문제도 구현 중 엄청 어려운 편에 속한다.

우선 나는 그렇다.

이건 진짜 어려웠다.

아니 알파고는 어떻게 계산함?

 

 

https://www.acmicpc.net/problem/16571

 

---

 

#맞은 풀이

#include <bits/stdc++.h>

using namespace std;


//게임은 누가먼저 시작하느냐에 따라 달라짐.
string answer;



//게임이 끝났는지(turn이 이기거나 지거나) 체크
//turn은 O 또는 X임
bool CheckGameEnd(vector<string>& board, char turn){

    //가로로 이겼는지
    for(int i = 0; i<3; i++){
        for(int j = 0; j<3; j++){
            if(board[i][j] != turn)break;

            if(j == 2) return true;
        }
    }

    //세로로 이겼는지
    for(int j = 0; j<3; j++){
        for(int i = 0; i<3; i++){
            if(board[i][j] != turn) break;

            if(i == 2) return true;
        }
    }

    //우하향 대각선으로 이겼는지
    for(int i = 0; i<3; i++){
        if(board[i][i] != turn)break;

        if(i == 2) return true;
    }


    //좌하향 대각선으로 이겼는지
    for(int i = 0; i<3; i++){
        if(board[i][2-i] != turn) break;

        if(i == 2) return true;
    }


    //누가 이기지 않았다면
    //게임이 진행중이거나 무승부임

    return false;
}


int DFS(char turn, vector<string>& board){
    
    //char의 덧셈 뺄셈은 int가 나오지만 (char)로 형변환할 수 있다.
    //turn이 이겼다면 => -1을 뱉는다
    //해당 진행상태는 종료되었고 그게 최선인지 확인해야 한다.
    if(CheckGameEnd(board, (char)('x' + 'o' - turn))){
        return -1;
    }
	
    //2를 한 이유는 0,1,-1만 나오게끔 하기 위해서다.
    int minVal = 2;

    for(int i = 0; i<3; i++){
        for(int j = 0; j<3; j++){

             //선택
            if(board[i][j] == '.'){

                board[i][j] = turn;

                //누구 차례인지 turn만빼면 됨 => 진행
                //해당 위치에 두었을 때 다시 게임을 진행한다.
                minVal = min(minVal, DFS((char)('x' + 'o' - turn), board));
                //상대방의 턴이되고 내가 둔 수에 상대방이 결국 진다면 dfs값으로 -1을 뱉는다.
                //내가 둔 모든 수에도 상대방이 이기면 dfs 값으로 1을 뱉는다.
                //복원
                board[i][j] = '.';
            }
        }
    }

    //minVal이 갱신되지 않으면 무승부다.
    //다른 브랜치에서도 0이나오면 무승부다 => 게임이 진행되었어도 마지막 브랜치에서 minVal이 갱신되지 않고
    //그렇게 되면 0을 return하며 끝이난다.
    if(minVal == 2 || minVal == 0){
        return 0;
    }
    
    //결국 상대방이 이기면 -1을 return
    //내가 이기면 1을 return 하게 된다.

    return -minVal;



}


string solution(vector<string> board)
{
    int cnt = 0;
    for(int i = 0; i<3; i++){
        for(int j = 0; j<3; j++){
            if(board[i][j] == 'x' || board[i][j] == 'o'){
                cnt++;
            }
        }
    }
	
    //x가 먼저 시작했다고 가정.
    //놓여진 개수가 짝수면 x차례
    //아니면 o 차례
    char start = 'x';
    if(cnt%2 == 1) start = 'o';
    int ret = DFS(start, board);


    if(ret == 1){
        if(start == 'o'){
            answer = "O";
        }else{
            answer = "X";
        }
    }
    if(ret == 0){
        answer = "D";
    }
    if(ret == -1){
        if(start == 'o'){
            answer = "X";
        }else{
            answer = "O";
        }
    }

    return answer;
}

//여기서 answer만 W,L로 바꾸면 그만이다.

int main(){

    //입력받아서
    char ans = soltution(board);
    
	return 0;
}