AlgoSpot) TICTACTOE

문제 : https://algospot.com/judge/problem/read/TICTACTOE

두명이 번갈아가면서 흑돌 백돌 대신 o와 x를 이용해서 오목이아닌 삼목을 하는데

판이 주어지고 두명이 최선을 다해서 플레이할때 누가 이기거나 비기는지 찾는 문제이다.

해당문제를 dp 없이 완전탐색으로 풀려 할 경우 많은 시간이 걸리므로 dp를 사용하기위해 해당문제를 모델링해야합니다.

board 판에 나올수있는 문자는 '.' , 'x' , 'o' 셋중 하나이므로 board판이 생길수 있는 경우의수는 3^9개이므로

19683(3^9)개의 int 배열을 이용해서 dp를 이용할수있습니다.

#include 
#include 
using namespace std;

char board[3][3];
char init_turn = 'x'; // true면 x턴 fasle면 o턴
int cache[19683];

// -1이면 진것 0 이면 비김 1이면 승리할수 있는걸로 판단한다.
bool isFinished(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 j = 0; j < 3; j++) {
		if (board[0][j] == turn && board[1][j] == turn && board[2][j] == 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;
}

int state_idx() { // 해당인덱스를 호출
	int ret = 0;
	for (int i = 0; i < 3; i++) {
		for (int j = 0; j < 3; j++) {
			ret *= 3;
			if (board[i][j] == 'o') ++ret;
			else if (board[i][j] == 'x') ret += 2;
		}
	}

	return ret;
}

int whoWin(char turn) {
	if (isFinished('x' + 'o' - turn)) return -1; // 상대방이 이미 한줄을 만든 경우

	int& ret = cache[state_idx()];

	if (ret != -2) return ret;

	int min_num = 2;

	for (int i = 0; i < 3; i++) {
		for (int j = 0; j < 3; j++) {
			if (board[i][j] == '.') {
				board[i][j] = turn;
				min_num = min(min_num, whoWin('x' + 'o' - turn));
				board[i][j] = '.';
			}
		}
	}

	if (min_num == 2 || min_num == 0) return ret = 0;
	return ret = -min_num;
}
int main() {
	std::ios::sync_with_stdio(false);
	//freopen("text.txt", "r", stdin);
	int C;
	cin >> C;
	int x_num, o_num;

	for (int i = 0; i < 19683; i++) cache[i] = -2; // 초기화

	while (C--) {
		x_num = o_num = 0;
		
		for (int i = 0; i < 3; i++) { // 시작 판 초기화
			for (int j = 0; j < 3; j++) {
				cin >> board[i][j];
				if (board[i][j] == 'x') ++x_num;
				else if (board[i][j] == 'o') ++o_num;
			}
		}

		if (x_num <= o_num) init_turn = 'x';
		else if (x_num > o_num) init_turn = 'o';
		
		int answer = whoWin(init_turn);

		if (init_turn == 'x') {
			if (answer == 1) {
				cout << "x" << endl;
			}
			else if (answer == 0) {
				cout << "TIE" << endl;
			}
			else if (answer == -1) {
				cout << "o" << endl;
			}
		}else if(init_turn == 'o'){
			if (answer == 1) {
				cout << "o" << endl;
			}
			else if (answer == 0) {
				cout << "TIE" << endl;
			}
			else if (answer == -1) {
				cout << "x" << endl;
			}
		}
		
	}// end of loop

	return 0;
}