TICTACTOE (중하, p. 337)

어떻게 풀었나?#

3x3 게임판과 player를 상태공간으로 두고 풀었음. (dp[board][player])

점화식 자체는 떠올리는게 쉬운데 구현이 좀 뻑뻑한 부분이 있음. 그리고 구현이 뻑뻑하니 당연히 맞다고 생각한 점화식도 이게 맞는건가 싶고.. 그러다보니 푸는데 시간이 좀 걸림. 풀면서 가장 많이 고민했던건, 매 수마다 최선을 다하는 방법을 고민해야할까? 였는데, 역시 그건 고민할 필요가 없었음. 현재 상태에서 player가 둘 수 있는 수를 다 둬보고, 그 중에서 이길 수 있는 경우가 한가지라도 있다면, 그 판은 이기는 판. 이기는 경우는 없는데 비기는 경우가 한가지라도 있다면, 그 판은 비기는 판. 그 외의 판은 모두 지는 판으로 결정하면 되는 것이었다.

정답 코드#

#include <bits/stdc++.h>
using namespace std;
vector<string> board;
struct Coord{
    int x,y;
};
bool IsWin(char player) {
    for(int i=0; i<3; i++) {
        int cnt=0;
        for(int j=0; j<3; j++) {
            if(board[i][j]==player) {
                cnt++;
            }
            else break;
        }
        if(cnt==3) return true;
    }
    for(int j=0; j<3; j++) {
        int cnt=0;
        for(int i=0; i<3; i++) {
            if(board[i][j]==player) {
                cnt++;
            }
            else break;
        }
        if(cnt==3) return true;
    }

    static const Coord co[2][3] = {
        {{0, 0}, {1, 1}, {2, 2}},
        {{0, 2}, {1, 1}, {2, 0}}
    };

    for(int i=0; i<2; i++) {
        int cnt=0;
        for(int j=0; j<3; j++) {
            if(board[co[i][j].x][co[i][j].y] == player) cnt++;
            else break;
        }
        if(cnt==3) return true;
    }

    return false;
}
inline int ToInt(char p) {
    if(p=='x') return 0;
    else if(p=='o') return 1;
    else return -1;
}
inline char ToChar(int pi) {
    if(pi==0) return 'x';
    else if(pi==1) return 'o';
    else return '.';
}
const int WIN = 0;
const int TIE = 1;
const int LOSE = 2;
map<vector<string>, int> dp[2];
int go(char p, vector<string> & b) {
    int pi = ToInt(p);
    if(dp[pi].count(b)) return dp[pi][b];
    else {
        if(IsWin(ToChar(ToInt(p)^1))) {
            return dp[pi][b] = LOSE;
        }
    }

    int & ret = dp[pi][b];
    ret = LOSE;
    bool ever_lose = false;
    for(int i=0; i<3; i++) {
        for(int j=0; j<3; j++) {
            if(b[i][j]=='.') {
                b[i][j]=p;
                int tmp = go(ToChar(pi^1), b);
                if(tmp == LOSE) {
                    b[i][j]='.';
                    return ret=WIN;
                }
                else if(tmp == TIE) {
                    ret=TIE;
                }
                else if(tmp == WIN) {
                    ever_lose = true;
                }
                b[i][j]='.';
            }
        }
    }
    if(!ever_lose) return ret=TIE;
    return ret;
}
int main() {
    ios::sync_with_stdio(false); cin.tie(0);
    int tc; cin >> tc;
    while(tc--) {
        board.clear();
        board.resize(3);
        dp[0].clear(); dp[1].clear();
        for(int i=0; i<3; i++) {
            cin >> board[i];
        }
        int xcnt=0, ocnt=0;
        for(int i=0; i<3; i++) {
            for(int j=0; j<3; j++) {
                if(board[i][j] == 'x') xcnt++;
                else if(board[i][j] == 'o') ocnt++;
            }
        }
        char player;
        if(xcnt == ocnt) player='x';
        else player='o';

        int res = go(player, board);
        if(res==WIN) printf("%c\n", player);
        else if(res==LOSE) printf("%c\n", ToChar(ToInt(player)^1));
        else puts("TIE");
    }
    return 0;
}

책의 풀이법을 참고한 코드#

여기까지 구하고 책에 있는 답을 보니 역시 훨씬 더 깔끔하게 구할 방법이 있었다.

상태공간의 표현에 player는 넣을 필요가 없었다.
player를 나타내는 ‘x’와 ‘o’를 계속 toggle해줘야 하는데, 나는 이걸 ToChar(ToInt(player)^1 형태로 표현했는데, 책에서는 ‘x’+’o’-player 형태로 표현함. 와.. 생각지도 못한 방법이네
WIN이 한번이라도 나오면 WIN, WIN이 안나왔는데 TIE가 한번이라도 나오면 TIE, 그 외는 LOSE인걸 나는 if문을 한참써서 해결했는데, 책에서는 이 의미를 순서대로 부여해서 그냥 min값을 assign하면서 갱신하도록 함.

책 참고하면서 코드 바꾸는데 첫번째 테케 결과가 TIE가 아닌 ‘x’로 계속 나와서 한참 헤맸음. 나중에 알고보니 return ret*=-1; 해줘야 했던건데, return -ret;해서 그랬던 거였음 ㅠ

#include <bits/stdc++.h>
using namespace std;
struct Coord{
    int x,y;
};
bool IsWin(vector<string> & b, char player) {
    for(int i=0; i<3; i++) {
        int cnt=0;
        for(int j=0; j<3; j++) {
            if(b[i][j]==player) {
                cnt++;
            }
            else break;
        }
        if(cnt==3) return true;
    }
    for(int j=0; j<3; j++) {
        int cnt=0;
        for(int i=0; i<3; i++) {
            if(b[i][j]==player) {
                cnt++;
            }
            else break;
        }
        if(cnt==3) return true;
    }

    static const Coord co[2][3] = {
        {{0, 0}, {1, 1}, {2, 2}},
        {{0, 2}, {1, 1}, {2, 0}}
    };

    for(int i=0; i<2; i++) {
        int cnt=0;
        for(int j=0; j<3; j++) {
            if(b[co[i][j].x][co[i][j].y] == player) cnt++;
            else break;
        }
        if(cnt==3) return true;
    }

    return false;
}
const int LOSE = -1;
const int TIE = 0;
const int WIN = 1;
vector<string> board;
map<vector<string>, int> dp;
int go(vector<string> & b, char p) {
    if(dp.count(b)) return dp[b];
    else {
        if(IsWin(b, 'x'+'o'-p)) {
            return dp[b] = LOSE;
        }
    }

    int & ret = dp[b];
    ret = 2;
    for(int i=0; i<3; i++) {
        for(int j=0; j<3; j++) {
            if(b[i][j]=='.') {
                b[i][j]=p;
                ret = min(ret, go(b, 'x'+'o'-p));
                b[i][j] = '.';
            }
        }
    }
    if(ret==2) ret=TIE;
    return ret*=-1;
}
int main() {
    ios::sync_with_stdio(false); cin.tie(0);
    int tc; cin >> tc;
    while(tc--) {
        board.clear(); board.resize(3);
        dp.clear();
        for(int i=0; i<3; i++) {
            cin >> board[i];
        }
        int xcnt=0, ocnt=0;
        for(int i=0; i<3; i++) {
            for(int j=0; j<3; j++) {
                if(board[i][j] == 'x') xcnt++;
                else if(board[i][j] == 'o') ocnt++;
            }
        }
        char player;
        if(xcnt == ocnt) player='x';
        else player='o';

        int res = go(board, player);
        if(res==WIN) printf("%c\n", player);
        else if(res==LOSE) printf("%c\n", 'x'+'o'-player);
        else puts("TIE");
    }
    return 0;
}