[백준/BOJ] 백준 16571번 : 알파 틱택토

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

16571번: 알파 틱택토

현재 플레이어가 승리하면 1, 무승부면 0, 패배하면 -1을 반환하는 함수를 만들었다 그러므로 다음 플레이어가 최대한 작은 값을 반환하도록 해야 한다. 그리고 map을 이용하여 같은 보드 상황의 값을 다시 계산하지 않도록 했다.

 

코드

#include <iostream>
#include <algorithm>
#include <vector>
#include <utility>
#include <map>
using namespace std;

//알고리즘 문제 해결 전략 책 공부 후 복습
vector<vector<int>> board(3, vector<int>(3, 0));
map<vector<vector<int>>, int> cache;
int cnt1 = 0;
int cnt2 = 0;
int player;
int output;

bool Finish()
{
	for (int i = 0; i < 3; i++)
	{
		bool ret = true;

		for (int j = 1; j < 3; j++)
		{
			if (board[i][j - 1] != board[i][j])
			{
				ret = false;
				break;
			}

			if (board[i][j] == 0)
			{
				ret = false;
				break;
			}
		}

		if (ret == true)
			return true;
	}

	for (int j = 0; j < 3; j++)
	{
		bool ret = true;

		for (int i = 1; i < 3; i++)
		{
			if (board[i - 1][j] != board[i][j])
			{
				ret = false;
				break;
			}

			if (board[i][j] == 0)
			{
				ret = false;
				break;
			}
		}

		if (ret == true)
			return true;
	}

	if (board[0][0] == board[1][1] && board[1][1] == board[2][2] && board[2][2] != 0)
		return true;

	if (board[0][2] == board[1][1] && board[1][1] == board[2][0] && board[2][0] != 0)
		return true;

	return false;
}

//현재 플레이어가 승리:1 무승부:0 패배:-1
int Solve(int here_player)
{
	//계산한적 있는 상황일때
	if (cache.count(board) != 0)
		return cache[board];

	//이전 플레이어가 3개 연속으로 만들었을때(현재 보드에 3개 연속으로 놓여 있을때)
	if (Finish() == true)
		return -1; //현재 플레이어는 지게 된다

	int next_ret = 987654321;
	for (int i = 0; i < 3; i++)
	{
		for (int j = 0; j < 3; j++)
		{
			//빈칸일때
			if (board[i][j] == 0)
			{
				board[i][j] = here_player;

				//상대 패배(-1)가 가장 좋은 경우이고, 그 다음 무승부(0)가 가장 좋은 결과 이므로
				//결과 값이 가장 작은 값을 찾는다
				if (here_player == 1)
					next_ret = min(next_ret, Solve(2));
				else
					next_ret = min(next_ret, Solve(1));

				board[i][j] = 0;
			}
		}
	}

	//바둑 돌을 둘 수 있는 자리가 없을때 (무승부)
	if (next_ret == 987654321)
		next_ret = 0;

	int ret;

	//뭘 해도 상대가 이기는 경우일때
	if (next_ret == 1)
		ret = -1;

	//상대가 무승부 나오는게 최선일때
	else if (next_ret == 0)
		ret = 0;

	//상대가 지는게 나올 수 있을때
	else if (next_ret == -1)
		ret = 1;

	cache.insert(make_pair(board, ret));

	return ret;
}

int main()
{
	cin.tie(NULL);
	ios_base::sync_with_stdio(false);

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

			if (input == 1)
				cnt1++;
			else if (input == 2)
				cnt2++;

			board[i][j] = input;
		}
	}

	if (cnt1 > cnt2)
		player = 2;
	else
		player = 1;

	output = Solve(player);

	if (output == 1)
		cout << "W";
	else if (output == 0)
		cout << "D";
	else
		cout << "L";

	return 0;
}