[알고스팟] 틱택토

문제링크

틱택토

• 문제
• 답안 제출
• 통계

문제 정보

• • 문제 ID
  • 시간 제한
  • 메모리 제한
  • 제출 횟수
  • 정답 횟수 (비율)
• • TICTACTOE
  • 1000ms
  • 65536kb
  • 896
  • 341 (38%)
• • 출제자
  • 출처
  • 분류
• • JongMan
  • 알고리즘 문제 해결 전략
  • 보기

문제

틱택토는 3x3 크기의 게임판에서 하는 3목 게임입니다. 두 명이 번갈아가며 o와 x를 게임판의 빈 칸에 쓰되, 먼저 같은 글자를 가로, 세로 혹은 대각선으로 3개 쓰이도록 하는 쪽이 이깁니다. 예를 들어, 다음 게임판은 x가 이긴 게임판입니다.

xoo
.x.
..x

게임은 항상 x부터 시작합니다.

틱택토 게임판의 현재 상태가 주어집니다. 두 사람 모두 최선을 다한다고 가정할 때, 어느쪽이 이길지 판단하는 프로그램을 작성하세요.

입력

입력의 첫 줄에는 테스트 케이스의 수 C(<= 50)가 주어집니다. 각 테스트 케이스는 세 줄에 각 세 글자로 게임판의 각 위치에 쓰인 글자가 주어집니다. 글자가 없는 칸은 마침표(.)로 표현합니다.

출력

각 테스트 케이스마다 한 줄을 출력합니다. 두 사람이 모두 최선을 다할 경우 비긴다면 TIE를, 아닌 경우 이기는 사람의 글자를 출력합니다.

예제 입력

3
...
...
...
xx.
oo.
...
xox
oo.
x.x

예제 출력

TIE
x
o

어떻게 풀까?

우선, 조합 게임의 특성을 알아야 합니다!

이전에 썼던 설명을 이용하겠습니다!

위 그림처럼, 마지막에 게임의 결과가 나올 것입니다. 이를 통해서, 전 단계가 A 차례 였다면,  A는 무조건 A가 이기는 결과를 선택할 것입니다. 

그렇다면, A 차례인 위 단계에서는 A가 이기는 결과가 될 것입니다.

이와 다르게 B차례에서 A가 이기는 결과로밖에 갈 수 없다면, B 차례의 상태에서는 A가 승리한다는 결과가 될 것입니다.

위와 같은 방식으로 한다면, 틱택토의 상태에 따라서 결과를 정할 수 있습니다.

다만, 틱택토에서는 비기는 결과도 있다는 것을 잊지 말아야 합니다!

그렇다면, 맵의 상태에 따라서 현재 차레가 'o'냐 'x'이냐에 따라서 다음과 같은 선택을 하게 됩니다.

1. 현재 상태와 다음 상태에서의 승리자가 같은 경우 : 현재 상태자의 승리로 현재 상태 끝

2. 현재 상태와 다음 상태에서가 비길 경우 : 지는 경우였을 경우 비기는 상태로 변경

3. 현재 상태와 다음 상태에서 질 경우 : 비기는 상태일 경우 비긴 상태로 하고, 지는 상태일 경우 변화 없음.

그리고, 이전에 어떤 경로로 'o'나 'x'가 놓여진건 상관 없이, 현재 말이 놓여진 상태만이 결과에 영향을 줍니다.

심지어, 틱택토의 'o'차례인지 'x'차례인지도 틱택토의 현재 맵 상태에 따라서 결정됩니다!

('x'가 먼저이기 때문이죠. 정확히는 빈 곳의 개수가 홀수 이면 x의 차례, 짝수개이면 o의 차례입니다.)

따라서, 메모이제이션은 그냥 맵의 현재 상황으로 저장할 수 있습니다!

그렇다면... 이제 중요한건 맵의 현재 상황을 어떻게 표현할 것인가가 되겠죠

하지만! 맵의 크기는 3x3의 9칸 밖에 없습니다.

또한, 맵의 상태는 아무것도 놓여진 '.'과 o가 놓여진 'o', x가 놓여진 'x' 3 가지로 표현이 가능합니다.

그렇다면 3 진법을 사용해서 맵을 나타낼 수 있겠죠! 

메모리도 3^9로 2만보다 작기 때문에 충분히 저장가능합니다.

이를 코드로 어떻게 만들까요?

코드

#include<cstdio>
#include<cstring>
char memoi[20000];
char map[3][4];
int conv[256], loser[256];
bool win() {
    bool res = false;
    for (int i = 0; i < 3; i++) {
        res |= map[i][0] != '.' && map[i][0] == map[i][1] && map[i][1] == map[i][2];
    }
    for (int j = 0; j < 3; j++) {
        res |= map[0][j] != '.' && map[0][j] == map[1][j] && map[0][j] == map[2][j];
    }
    res |= map[1][1] != '.' && map[0][0] == map[1][1] && map[0][0] == map[2][2];
    res |= map[1][1] != '.' && map[2][0] == map[1][1] && map[2][0] == map[0][2];
    return res;
}
int getState() {
    int state = 0;
    for (int i = 0; i < 3; i++) {
        for (int j = 0; j < 3; j++) {
            state *= 3;
            state += conv[map[i][j]];
        }
    }
    return state;
}
char winner(int depth, char turn) {
    char &ret = memoi[getState()];
    if (ret != -1) return ret;
    if (win()) {
        return ret = loser[turn];
    }
    if (depth == 9) return ret = 0;
    ret = loser[turn];
    for (int i = 0; i < 3; i++) {
        for (int j = 0; j < 3; j++) {
            if (map[i][j] == '.') {
                map[i][j] = turn;
                char w = winner(depth + 1, loser[turn]);
                map[i][j] = '.';
                if (w == turn) {
                    ret = turn;
                    return ret;
                }
                else if (w == 0) {
                    ret = 0;
                }
            }
        }
    }
    return ret;
}
int main() {
    int t;
    scanf("%d\n", &t);
    
    memset(memoi, -1, sizeof(memoi));
    conv['.'] = 0;
    conv['o'] = 1;
    conv['x'] = 2;
    loser['o'] = 'x';
    loser['x'] = 'o';
    int depth = 0;
    for (int tc = 1; tc <= t; tc++) {
        for (int i = 0; i < 3; i++) {
            scanf("%s\n", map[i]);
        }
        for(int i = 0; i < 3; ++i){
            for(int j = 0; j <3; ++j){
                depth += map[i][j] != '.';
            }
        }
        int cnt = 0;
        for (int i = 0; i < 3; i++) {
            for (int j = 0; j < 3; j++) {
                cnt += map[i][j] == '.';
            }
        }
        char res = winner(depth, cnt & 1 ? 'x' : 'o');
        if (res == 0) printf("TIE\n");
        else {
            printf("%c\n", res);
        }
    }
    return 0;
}
 

여담

시간 복잡도는 어떨까요?

메모이제이션이 3^9이고, 각 행마다 3^2 의 반복문을 가지기 때문에

3^11의 시간복잡도를 가질것입니다!

무려 O(1) 입니다.