[BOJ 7682 // C++] 틱택토

※ 글쓴이는 취미로 코딩을 익혀보는 사람이라 정확하지 않은 내용을 담고 있을 수 있다 ※

 

이번에 볼 문제는 백준 7682번 문제인 틱택토이다.
문제는 아래 링크를 확인하자.

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

7682번: 틱택토

각 칸의 상태는 ".", "O", "X"의 세 가지 상태가 가능하므로 살펴보아야 할 틱택토의 경우의 수는 많아야 3^9 = 19683가지가 된다. 따라서, 직접 틱택토 게임을 시뮬레이션을 돌려 가능한 최종상태들을 집합으로 전처리하고 문제를 해결할 수 있다.

 

아래는 제출한 소스코드이다.

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

set<string> valid_game;

bool finished(string& s) {
	if (s[0] != '.' && s[0] == s[1] && s[1] == s[2]) return 1;
	if (s[3] != '.' && s[3] == s[4] && s[4] == s[5]) return 1;
	if (s[6] != '.' && s[6] == s[7] && s[7] == s[8]) return 1;
	if (s[0] != '.' && s[0] == s[3] && s[3] == s[6]) return 1;
	if (s[1] != '.' && s[1] == s[4] && s[4] == s[7]) return 1;
	if (s[2] != '.' && s[2] == s[5] && s[5] == s[8]) return 1;
	if (s[0] != '.' && s[0] == s[4] && s[4] == s[8]) return 1;
	if (s[2] != '.' && s[2] == s[4] && s[4] == s[6]) return 1;

	return 0;
}

void func(string& s, int turn) {
	if (valid_game.find(s) != valid_game.end()) return;
	if (finished(s)) {
		valid_game.insert(s);
		return;
	}
	bool chk = 1;
	if (turn == 0) {
		for (int i = 0; i < 9; i++) {
			if (s[i] == '.') {
				string ss = s; ss[i] = 'X';
				func(ss, 1);
				chk = 0;
			}
		}
	}
	else {
		for (int i = 0; i < 9; i++) {
			if (s[i] == '.') {
				string ss = s; ss[i] = 'O';
				func(ss, 0);
				chk = 0;
			}
		}
	}

	if (chk) valid_game.insert(s);
}

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

	string tmp = ".........";
	func(tmp, 0);
	
	cin >> tmp;
	while (tmp != "end") {
		if (valid_game.find(tmp) == valid_game.end()) cout << "invalid\n";
		else cout << "valid\n";
		cin >> tmp;
	}
}