백준 7682번 - 틱택토 (C++)

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

7682번: 틱택토

 

두가지 풀이법이 있다. 틱택토의 모든 조건을 따져 지금 들어온 틱택토가 유효한지 확인하는 방법과 모든 시뮬레이션을 해보고 들어온 틱택토가 있는지 확인하는 방법이다. 이전의 방법은 많은 블로그에서 소개하고 있기 때문에 난 두번째 방법으로 해보았다. 

 

시간 복잡도는 9^9 로 충분히 가능하다. 그리고 문자열을 방문표시해야하는 짜증이 있었는데 이것을 셋으로 표현했다. 맵으로 표현했을 때 안되는 이유가 도저히 뭔지 모르겠다.. 방법이 분명 있을 것 같은데..

 

아무튼 시간 복잡도는 

 

9^9 * log(9^9)

 

이렇게 된다. 로그가 붙는 이유는 짜증나게 셋의 파인드를 이용하기 때문이다. 

 

#include <iostream>
#include <vector>
#include <map>
#include <queue>
#include <set>
using namespace std;

set<string> check;

bool endCheck(string str, char turn){
    if((str[0] == str[1] && str[1] == str[2]) && str[0] == turn ) return true;
    if((str[3] == str[4] && str[4] == str[5]) && str[3] == turn ) return true;
    if((str[6] == str[7] && str[7] == str[8]) && str[6] == turn ) return true;
    if((str[0] == str[3] && str[3] == str[6]) && str[0] == turn ) return true;
    if((str[1] == str[4] && str[4] == str[7]) && str[1] == turn ) return true;
    if((str[2] == str[5] && str[5] == str[8]) && str[2] == turn ) return true;
    if((str[0] == str[4] && str[4] == str[8]) && str[0] == turn ) return true;
    if((str[2] == str[4] && str[4] == str[6]) && str[2] == turn ) return true;
    
    return false;
}

queue<pair<pair<string, char>, int>> q; // 현재 상황, 턴

void bfs(){
    while(!q.empty()){
        string ttt = q.front().first.first;
        char turn = q.front().first.second;
        int cnt = q.front().second;
        q.pop();

        if(check.find(ttt) != check.end()) continue;
        if(cnt == 9){
            check.insert(ttt);
            continue;
        }

        for (int i = 0; i < 9; i++){
            string nextstr = ttt;

            if(nextstr[i] == '.'){
                nextstr[i] = turn;
                if(endCheck(nextstr, turn)){
                    check.insert(nextstr);
                }else{
                    if(turn == 'O') q.push({{nextstr, 'X'}, cnt + 1});
                    else q.push({{nextstr, 'O'}, cnt + 1});
                }
            }
        }
    }
}

int main(){   
   q.push({{".........", 'X'}, 0}); 
    bfs();

    while(true){
        string tmp;
        cin >> tmp;

        if(tmp == "end") break;

        if(check.find(tmp) != check.end()){ // 찾음
            cout << "valid" << '\n';
        }else{
            cout << "invalid" << '\n';
        }
    }
}

 

위가 완전탐색, 아래가 구현을 통한 방식이다. 확실히 구현을 통한 방식이 훨씬 시간, 메모리적으로 이득이다.