[백준 7682번] 틱택토

문제 링크: https://www.acmicpc.net/problem/7682

7682번: 틱택토

<문제 풀이> DFS, 순열, 백트랙킹 알고리즘

 

각 테스트 케이스에 대해서 해당 케이스가 가능한 틱택토 경우의 수인지 판단하는 방법은 9개의 위치에 토큰을 놓는 순열을 구하면 됩니다.

 

9개의 위치에 토큰을 놓는 순열을 구하면 경우의 수는 9! = 362880입니다

가능한 순열을 state[362880][3][3] 배열에 하나씩 저장하고 테스트 케이스가 이 배열 안에 존재하는 지만 판단하면 끝입니다.

 

DFS로 모든 순열을 구할 때 두 가지 매개 변수가 필요합니다.

1. k : DFS 깊이를 추적하기 위함 -> k = 9가 되는 경우는 게임판을 모두 채운 경우입니다.

2. nextToken :  X, O 토큰을 번갈아가면서 놓기 위함

 

DFS의 base case는 게임이 끝날 때 즉, k = 9가 되거나 가로, 세로, 대각선 방향으로 3칸을 잇는 데 한 토큰만을 사용한 경우입니다.

 

가로, 세로, 대각선 방향으로 3칸을 잇는 경우 종료하는 조건이 있으니깐 실제로는 9! 보다 더 적은 경우의 수가 나옵니다.

 

 

 

 

<C++소스코드>

#include <iostream>
#include <algorithm>
#include <string>
using namespace std;
 
int state[362880][3][3];
char board[3][3];
int cnt = 0;
 
 
bool isGameDone(int k) { 
    if (board[0][0] != '.' && board[0][0] == board[1][1] && board[1][1] == board[2][2]) return true; // 대각선
    else if (board[2][0] != '.' && board[2][0] == board[1][1] && board[1][1] == board[0][2]) return true; // 대각선
    else if (board[0][0] != '.' && board[0][0] == board[0][1] && board[0][1] == board[0][2]) return true; // 나머지 가로 세로 
    else if (board[1][0] != '.' && board[1][0] == board[1][1] && board[1][1] == board[1][2]) return true;
    else if (board[2][0] != '.' && board[2][0] == board[2][1] && board[2][1] == board[2][2]) return true;
    else if (board[0][0] != '.' && board[0][0] == board[1][0] && board[1][0] == board[2][0]) return true;
    else if (board[0][1] != '.' && board[0][1] == board[1][1] && board[1][1] == board[2][1]) return true;
    else if (board[0][2] != '.' && board[0][2] == board[1][2] && board[1][2] == board[2][2]) return true;
    else if (k == 9) return true; // 판이 가득 찬 경우 
    else return false; // 그 외 게임을 계속할 수 있다.
}
 
//nextToken = 'X' or 'O'
void dfs(int k, char nextToken) {
    if (isGameDone(k)) {
        for (int i = 0; i < 3; i++) {
            for (int j = 0; j < 3; j++) {
                state[cnt][i][j] = board[i][j];
            }
        }
        cnt++;
        return;
    }
 
    for (int i = 0; i < 3; i++) {
        for (int j = 0; j < 3; j++) {
            if (board[i][j] != '.') continue; // 이미 토큰이 있으면 무시
            board[i][j] = nextToken;
            if (nextToken == 'O') dfs(k + 1, 'X'); //현재 위치에 토큰을 놓았을 때 다음 위치는 다른 토큰을 놓아야한다.
            else if (nextToken == 'X') dfs(k + 1, 'O');
            board[i][j] = '.'; //모든 순열을 구하기 위해, 이미 구한 경우의 수는 제거
        }
    }
 
}
 
 
//가능한 조합인지 확인
bool isValid() {
    for (int k = 0; k < 362880; k++) {
        int ret = true;
        for (int i = 0; i < 3; i++) {
            if (!ret) break;
            for (int j = 0; j < 3; j++) {
                if (!ret) break;
                if (board[i][j] != state[k][i][j]) {
                    ret = false;
                    break;
                }
            }
        }
        if (ret) return true;
    }
    return false;
}
 
int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL); cout.tie(NULL);
 
    fill(&board[0][0], &board[2][3], '.');
    dfs(0, 'X');
 
    while (true) {
        string s; cin >> s;
        if (s == "end") break;
        int index = 0;
        for (int i = 0; i < 3; i++) {
            for (int j = 0; j < 3; j++) {
                board[i][j] = s[index++];
            }
        }
        if (isValid()) cout << "valid\n";
        else cout << "invalid\n";
    }
    cout << cnt;
    return 0;
 
 
 
}