백준 7682 - 틱택토

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

골드 5 구현 문제

 

골드 답게 구현이 까다롭고 조건이 많이 달리는 문제인것 같다.

 

게임의 상태가 끝나는 것을 결정할 수 있는 조건을 분류해서

이 조건에 부합하지 않는 경우에 대해 모두 false를 반환하도록 처리하고 

모든 조건을 충족하는 경우 true를 반환하도록 해서 valid와 invalid를 판단했다.

 

내가 생각한 조건들은 다음과 같다.

 

- X와 O의 개수는 같거나 X가 하나 더 많은 경우만 가능하다.

X가 선공이기 때문에

O가 이겼다면 O가 놓는 차례에서 끝나기 때문에 O,X의 수가 같다.

X가 이겼다면 X가 놓는 차례에서 끝나기 때문에 O보다 X의 수가 1더 많다.

 

- X가 2줄을 만드는 경우는 가능하지만, O가 2줄을 만드는 경우는 불가능하다.

X는 한 점을 공유하면서 2줄을 만들수 있다. 공유하는 점에 마지막으로 둔다고 생각하면 가능한 케이스이다.

그러나 한 점을 공유하면서 2줄을 만드는 경우에도 9칸중에 5칸이 필요하기 때문에

O가 2줄을 만드는 경우는 위의 조건으로 인해 불가능하다.

 

- 둘 다 이기는 경우는 불가능하다.

당연히 한쪽이 이기면 그상태에서 게임이 끝났어야 하므로 정상적인 게임판 상황이 아니다.

 

- 둘 다 이기지 못하는 경우는 가능하다.

입력으로 주어진 케이스에 있었음. 그러나 무승부로 끝나기 위해서는 판에 더이상 둘 곳이 없어야 하므로

O와 X의 합이 9여야 하고, X가 O보다 1개 더 많아야 한다.

 

이를 토대로 구현한 코드는 다음과 같다.

#include <bits/stdc++.h>

using namespace std;

using ll = long long;
using ull = unsigned long long;
using pii = pair<int, int>;
using tiii = tuple<int, int, int>;
const int INF = 0x3f3f3f3f;
const int MOD = 1'000'000'007;

// 내가 틀린 부분. 승리한 녀석에 대해 체크할때 '.'인 경우도 else에 포함된다는 점을 놓침.
bool CheckIsEnd(string s)
{
	//일단 X가 이겼는지 Y가 이겼는지 검사한다.
	int o = 0;
	int x = 0;
	for (auto c : s)
	{
		if (c == 'O')
			o++;
		else if (c == 'X')
			x++;
	}
	bool IsOWin = false;
	bool IsXWin = false;
	for (int i = 0; i < 3; i++)
	{
		if (s[i * 3] == s[i * 3 + 1] && s[i * 3 + 1] == s[i * 3 + 2])
		{
			if (s[i * 3] == 'O')
				IsOWin = true;
			else if(s[i * 3] == 'X')
				IsXWin = true;
			
		}
		if (s[i] == s[3 + i] && s[3 + i] == s[6 + i])
		{
			if (s[i] == 'O')
				IsOWin = true;
			else if(s[i] == 'X')
				IsXWin = true;
		}
	}
	if (s[0] == s[4] && s[4] == s[8])
	{
		if (s[0] == 'O')
			IsOWin = true;
		else if(s[0] == 'X')
			IsXWin = true;
	}
	if (s[2] == s[4] && s[4] == s[6])
	{
		if (s[2] == 'O')
			IsOWin = true;
		else if (s[2] == 'X')
			IsXWin = true;
	}

	//둘다 이기는 경우는 없어.
	if (IsOWin && IsXWin)
		return false;
	else if (IsOWin) // O가 이겼을 때는 O와 x의 수가 같아야 한다.
	{
		if (o != x)
		{
			return false;
		}
	}
	else if (IsXWin) // X가 이겼을 때는 O보다 X의 수가 하나 더 많아야 한다.
	{
		if (o+1 != x)
		{
			return false;
		}
	}
	else
	{
		if (x + o != 9 || o + 1 != x)
		{
			return false;
		}
	}
	
	return true;
}

int main()
{
	ios::sync_with_stdio(false);
	cin.tie(0);

	string s;
	vector<string> ans;
	while(cin >> s)
	{
		if (s == "end") break;
		if (CheckIsEnd(s) == false)
		{
			ans.push_back("invalid");
		}
		else
		{
			ans.push_back("valid");
		}
	}
	for (auto str : ans)
	{
		cout << str;
		cout << '\n';
	}

	return 0;
}

1. X, O가 1줄을 완성한 경우가 있는지를 먼저 검사.

2. 둘다 1줄이 완성된 경우면 return false;

3. X가 이겼으면 x == o+1인지, O가 이겼으면 x == o 인지 검사해서 아닌경우 return false;

4. 둘 다 1줄을 완성하지 못한 경우 (x+o == 9 && o+1 == x) 가 아닌경우 return false;

5. 다 통과한 경우 return true;