[BOJ]백준 7682번: 틱택토(C++)/BackTracking

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

7682번: 틱택토

출처: https://upload.wikimedia.org/wikipedia/commons/thumb/3/32/Tic_tac_toe.svg/langko-300px-Tic_tac_toe.svg.png

틱택토 보드판의 상태를 입력받아서 종료 조건으로 가능한 경우인지 판단하는 문제

그냥 백트래킹으로 맨 처음에 모든 틱택토 경우의 수(958가지)를 구해서 map에 저장해주고 입력받은 문자열이 map에 있는지로 판단해주었다

문제푸는걸 쉬었다가 시작해서 그런가?? 요즘 문제 처음볼 때 마다 막막하다 ㅠ.ㅜ

#include <iostream>
#include <string>
#include <map>
#define board(i,j) str[(i)*3+j]
using namespace std;

map<string, bool> m;
string str = ".........";
bool ans = false;

bool finish() {
	for (int i = 0; i < 3; i++) {
		int cnt[2] = { 0,0 };
		char c[2] = { board(i, 0), board(0, i) };
		for (int j = 0; j < 3; j++) {
			if (board(i, j) == '.')cnt[0] = 0;
			else if (board(i, j) == c[0])cnt[0]++;
			else cnt[0] = 1;
			if (board(j, i) == '.')cnt[1] = 0;
			else if (board(j, i) == c[1])cnt[1]++;
			else cnt[1] = 1;
		}
		if (cnt[0] == 3 || cnt[1] == 3)
			return true;
	}
	if (board(0, 0) != '.' && (board(0, 0) == board(1, 1)) && (board(1, 1) == board(2, 2)))
		return true;
	if (board(0, 2) != '.' && (board(0, 2) == board(1, 1)) && (board(1, 1) == board(2, 0)))
		return true;
	return false;
}

void func(char turn, int dep) {
	if (finish() || dep == 9) {
		m.insert(make_pair(str, true));
		return;
	}
	for (int i = 0; i < 3; i++)
		for (int j = 0; j < 3; j++)
			if (board(i, j) == '.') {
				board(i, j) = turn;
				if (turn == 'X')func('O', dep + 1);
				if (turn == 'O')func('X', dep + 1);
				board(i, j) = '.';
			}
}

int main() {
	func('X', 0);
	while (1) {
		cin >> str;
		if (str == "end")break;

		if (m.find(str) != m.end())cout << "valid\n";
		else cout << "invalid\n";

	}
	return 0;
}