BOJ 7682

27 Jan 2020 • ProblemSolving

틱택토

문제출처

1.설계(10)

  • 문제 해석

    • 비어있는 3 x 3 배열을 X와 O로 채우는 게임입니다.
    • 첫번째 사람이 X, 두번째 사람이 O를 놓는데 한사람의 말이 가로, 세로, 대각선 방향으로 3칸을 잇는데 성공하거나 게임판이 가득차면 게임이 끝나게 됩니다.
    • 주어진 게임판의 상태가 게임 중 가능한 상태인지 체크하는 문제입니다.

  • 설계

    • 각 3 x 3 배열에 X,O,. 중 하나가 들어가므로 3^(3x3+1)-1 가지의 경우의 수가 나올 수 있습니다.
    • X를 1, O를 2로하는 3진수 형태로 변환해 주어진 상태를 백트래킹으로 체크하도록 하였습니다.

2.구현(50)

  • 코드
#include <iostream>


#define MAXN 60000

using namespace std;

bool state[MAXN];
int map[3][3];
bool check_state() {
	for (int i = 0; i < 3; i++) {
		int j = 0;
		int target = map[i][j];
		bool flag = false;
		if (target != 0) {
			for (j = 1; j < 3; j++) {
				if (map[i][j] != target) {
					flag = true;
					break;
				}
			}
			if (!flag) return true;
		}
		
		flag = false;
		j = 0;
		target = map[j][i];
		if (target != 0) {
			for (j = 1; j < 3; j++) {
				if (map[j][i] != target) {
					flag = true;
					break;
				}
			}
			if (!flag) return true;
		}	
	}
	if (map[0][0] != 0 && map[0][0] == map[1][1] && map[1][1] == map[2][2]) return true;
	if (map[0][2] != 0 && map[0][2] == map[1][1] && map[1][1] == map[2][0]) return true;
	for (int i = 0; i < 3; i++) {
		for (int j = 0; j < 3; j++) {
			if (map[i][j] == 0) return false;
		}
	}
	return true;
}

void make_state() {
	int now = 0;
	for (int i = 0; i < 3; i++) {
		for (int j = 0; j < 3; j++) {
			now = now * 3 + map[i][j];
		}
	}
	state[now] = true;
}
void dfs(int cnt) {
	
	if (check_state()) {
		make_state();
		return;
	}
	for (int i = 0; i < 3; i++) {
		for (int j = 0; j < 3; j++) {
			if (map[i][j] != 0) continue;
			map[i][j] = cnt + 1;
			dfs((cnt + 1) % 2);
			map[i][j] = 0;
		}
	}
}
int main() {
	ios::sync_with_stdio(false);
	cin.tie(0);
	dfs(0);
	while (1) {
		string s;
		cin >> s;

		if (s == "end") break;
		int now = 0;
		for (int i = 0; i < s.length(); i++) {
			if (s[i] == 'X') {
				now = now * 3 + 1;
			}
			else if (s[i] == 'O') {
				now = now * 3 + 2;
			}
			else {
				now = now * 3;
			}
		}
		if (state[now]) printf("valid\n");
		else printf("invalid\n");
	}
	return 0;
}

  • 디버깅

    • 모든 가능한 경우의 수를 체크하고, 테스트를 하는식으로 구현하고 제출했더니 WA가 나왔습니다.
    • SLPC2006대회에서 제공하는 테스트케이스로 확인을 해보니, check_state 함수에서 가로를 체크 한 후 세로를 체크할 때, flag를 false로 갱신을 시켜주지 않아서 문제가 발생했습니다.

  • 제출결과

    20ms

3.마무리

  • 단순히 백트래킹기법을 이용하여 map을 그릴 수 있는 문제였고, 해당 상태를 3진수로 표현하는 아이디어를 생각치 못하면 어려울 수도 있는 문제 였던 것 같습니다.
 BOJ  SLPC2006

Related Posts