boj, 백준) 7682. 틱택토 ( C / C++ )

1. 문제 링크

www.acmicpc.net/problem/7682

7682번: 틱택토

2. 문제 개요

틱택토 게임을 한다. 규칙은 3x3 판에 X, O 말을 번갈아 놓고, X가 먼저 놓는다. 이때, 먼저 자신의 표시 3개를 한 줄로 만드는 사람이 승리한다.

게임판의 상태가 주어지면, 그 상태가 틱택토 게임에서 발생할 수 있는 최종 상태인지를 판별하시오.

 

 

3. 문제 힌트

(1) X가 승리할 때, O가 승리할 때, 비길 때, 그 외 이 4가지 경우로 생각해보자.

 

(2) 백트래킹으로 직접 게임을 진행하면서 목표 상태(주어진 판)에 도달할 수 있는지 구현하는 방법.

 

->1번이 더 간단.

 

4. 문제 풀이

처음에 (1)번과 같은 풀이도 생각해보았다. 그런데, 왠지 모르게 함정이 있을 것 같아서 백트래킹 방식으로 구현을 해보았다. 

백트래킹으로 코딩을 해보다가.. 시간이 도중에 조금 아까워서 방향을 도중에 바꿨다. 물론.. 조금 삐끗한 부분도 있었지만 여튼 한 번만에 깔끔하게 안 돼서... (더 짧고 간결하게 짜려다 보니 일단 문제 풀고 나서 뒤에 이 방법으로도 해보자 라고 생각)

 

그래서!

단순 구현방식으로 구현할 때 고려할 점은

 

X가 승리할 때,

O가 승리할 때,

비길 때,

그 외,

이렇게 4가지로 분류할 수 있다.

조건을 조금 더 깊게 살펴보면,

 

→X가 승리할 때,

   X는 3줄이 존재해야 함. O는 3줄이 존재하면 안 됨. X는 O보다 1개가 더 많아야 함.

 

→O가 승리할 때,

   X는 3줄이 존재하면 안됨. O는 3줄이 존재해야 함. O와 X의 개수는 같아야 함.

 

→비길 때,

   X도 O도 3줄이 존재하면 안됨. X는 5개 O는 4개여야 함.

 

→그 외,

 

위의 조건만 잘 구현해주면 된다.

3줄이 존재하는지는 3x3배열을 모두 가로 3번 세로 3번 대각선 2번 검사해주면 된다.

 

코드에서 1번의 map탐색으로 x, o중 어는 것이 3줄이 존재하는지 0, 1, 2, 3... 과 같은 구분자로 받아서 해결할 수 있었으나, 2번 반복해서 구해도 시간 초과가 날 것 같지 않아 직관적인 코드로 보일 수 있도록 따로 구현했다.

 

map 탐색시 조건에 맞으면 바로 return 해도 괜찮다.

 

5. 코드

#include <iostream>
#include <string>
using namespace std;

char map[3][3];
string input;

bool CheckXwin() 
{
	bool ret = false;
	for (int i = 0; i < 3; ++i)
		if (map[i][0] == 'X' && map[i][0] == map[i][1] && map[i][1] == map[i][2])
			ret = true;
	for (int j = 0; j < 3; ++j)
		if (map[0][j] == 'X' && map[0][j] == map[1][j] && map[1][j] == map[2][j])
			ret = true;

	if (map[0][0] == 'X' && map[0][0] == map[1][1] && map[1][1] == map[2][2])
		ret = true;

	if (map[0][2] == 'X' && map[0][2] == map[1][1] && map[1][1] == map[2][0])
		ret = true;

	return ret;
}

bool CheckOwin()
{
	bool ret = false;
	for (int i = 0; i < 3; ++i)
		if (map[i][0] == 'O' && map[i][0] == map[i][1] && map[i][1] == map[i][2])
			ret = true;
	for (int j = 0; j < 3; ++j)
		if (map[0][j] == 'O' && map[0][j] == map[1][j] && map[1][j] == map[2][j])
			ret = true;

	if (map[0][0] == 'O' && map[0][0] == map[1][1] && map[1][1] == map[2][2])
		ret = true;

	if (map[0][2] == 'O' && map[0][2] == map[1][1] && map[1][1] == map[2][0])
		ret = true;

	return ret;
}


int main()
{
	cin >> input;

	while(input != "end")
	{
		int onum = 0, xnum = 0;
		bool owin = false, xwin = false;

		for (int i = 0; i < 9; ++i){
			map[i / 3][i % 3] = input[i];
			if (input[i] == 'O')
				++onum;
			else if (input[i] == 'X')
				++xnum;
		}

		owin = CheckOwin();
		xwin = CheckXwin();

		if (xwin && !owin && xnum - onum == 1){
			//x가 이기는 경우
			cout << "valid\n";
		}
		else if (!xwin && owin && onum == xnum) {
			//o가 이기는 경우
			cout << "valid\n";
		}
		else if (!xwin && !owin && xnum == 5 && onum == 4){
			//비기는 경우
			cout << "valid\n";
		}
		else{
			//그 외,
			cout << "invalid\n";
		}

		cin >> input;
	}
	return 0;
}

 

 

6. 결과