[Algospot] 틱택토 (문제 ID : TICTACTOE)

문제

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

xoo

.x.

..x

게임은 항상 x부터 시작합니다.

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

 

입력

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

 

출력

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

---

난이도는 하라고 하지만 그래도 어려운 문제이다. 게임판에 x, o, . 총 세가지가 9개 올 수 있기 때문에 3^9개의 배열을 사용해 문자판 자체를 메모이제이션한다. 그러기 위해 bijection함수를 통해 게임판을 정수로 전환한다. 게임의 승,패 여부는 canWin함수를 통해 계산한다. 기저사례로 상대방에 의해 게임이 종료되면 패배하기 때문에 -1을 반환한다. 그 후엔 게임판의 빈 공간에 직접 칸을 채우며 점수를 계산한다.

 

 

코드 원본 : https://github.com/chosh95/STUDY/blob/master/Algospot/TICTACTOE.cpp

chosh95/STUDY

C++ 코드

#include <iostream>
#include <cstring>
#include <algorithm>
#include <vector>
#include <map>
using namespace std;
int C;
int dp[19628]; //3^9
int bijection(const vector<string>& board)
{
	int res = 0;
	for (int i = 0; i < 3; i++) {
		for (int j = 0; j < 3; j++) {
			res *= 3;
			if (board[i][j] == 'o') ++res;
			else if (board[i][j] == 'x') res += 2;
		}
	}
	return res;
}
bool isFinished(const 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 i = 0; i < 3; i++){
		for (int j = 0; j < 3; j++){
			if (board[j][i] != turn)break;
			if (j == 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 canWin(vector<string>& board, char turn)
{
	if (isFinished(board, 'o'+'x'-turn)) return -1;
	int& res = dp[bijection(board)];
	if (res != -2) return res;
	int minValue = 2;
	for (int i = 0; i < 3; i++) {
		for (int j = 0; j < 3; j++) {
			if (board[i][j] == '.') {
				board[i][j] = turn;
				minValue = min(minValue, canWin(board, 'o'+'x'-turn));
				board[i][j] = '.';
			}
		}
	}
	if (minValue == 2 || minValue == 0) return res = 0;
	return res = -minValue;
}


int main()
{
	cin >> C;
	while (C--) {
		int cnt = 0;
		vector<string> board;
		string tmp;

		for (int i = 0; i < 19628; i++) dp[i] = -2;

		for (int i = 0; i < 3; i++) {
			cin >> tmp;
			for (int j = 0; j < 3; j++) {
				if (tmp[j] != '.') cnt++;
			}
			board.push_back(tmp);
		}
		char start = 'x';
		if (cnt % 2 == 1) start = 'o';

		int res = canWin(board, start);
		if (res == 1) cout << start << endl;
		else if (res == 0) cout << "TIE" << endl;
		else cout << (char)('x' + 'o' - start) << endl;
	}
}