[백준, C++] 7682 - 틱택토

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

7682번: 틱택토

 

문제 분석

도대체 이 문제가 왜 골드 5인지 이해할 수가 없다. 나는 틱택토에 대해서 알고 있어서 문제를 빠르게 이해한 것일 수도 있다(옛날에 Android MVC, MVP, MVVM을 공부할 때 틱택토 샘플 앱을 본 적이 있어서 그럴수도 ? 틱택토에 대한 이해도가 부족하다면, 혹은 문제가 무슨 말을 하는지 모르겠다면 직접 틱택토를 플레이해보고 오는 것도 좋은 것 같다. 구글에 틱택토 를 검색하면 바로 플레이해볼 수 있다).

 

단순히 순서대로 분기처리해서 조건을 체크해보면 된다고 생각했다.

 

1. O와 X 개수 카운팅으로 invalid를 걸러낼 수 있다.

틱택토는 X가 선공, O가 후공인 체계이다. 즉, X와 O의 개수가 동일하거나(짝수 턴 직후), X가 O보다 1개 더 많은 경우(홀수 턴 직후)만 유효하고 나머지는 모두 유효하지 않다.

2. O와 X 개수 카운팅을 기반으로, 이미 승리조건을 달성했음에도 게임을 더 진행했다고 판단되면 invalid로 걸러낼 수 있다.

X가 O보다 1개 더 많은 경우, 즉 홀수 턴 직후 틱택토 게임판을 확인했는데 O가 승리인 경우는 유효하지 않다. 왜냐면 O가 두고 곧바로(짝수 턴 직후에) 게임이 끝났어야 하기 때문이다.

X와 O의 개수가 동일한 경우, 즉 짝수 턴 직후 틱택토 게임판을 확인했는데 X가 승리인 경우는 유효하지 않다. 왜냐면 X가 두고 곧바로(홀수 턴 직후에) 게임이 끝났어야 하기 때문이다.

3. 틱택토 게임판이 최종 상태인지(X / O 승리 or 무승부)를 체크해 valid / invalid로 처리할 수 있다.

지금까지는 게임 진행 중 일어날 수 없는 상황인지 아닌지를 체크했다. 여기까지 왔다면, 최소한 게임 중 일어날 수 없는 일이 일어나지는 않았던 것이다.

 

그렇다면 이제 최종 상태인지만 확인하면 된다. O나 X가 이겼거나, 마지막 턴까지 게임을 진행을 완료했다면 valid이다. 하지만 그렇지 않고 '.'로 표시된 빈칸이 있다면 invalid이다.

 

실제로 이 풀이를 그대로 코드로 옮겼다. 그래서 골드 문제라고 생각되지 않는 ... 그런 상황 ?

 

코드

#include <iostream>
#include <cstring>

using namespace std;

string input;
string result;

void getInput();
void solve();
void printResult();

bool isWin(char);
bool isFinished();

int main() {
    cin.tie(NULL);
    ios::sync_with_stdio(false);

    while (true) {
        getInput();
        if (input == "end") {
            break;
        }
        solve();
        printResult();
    }

    return 0;
}

void getInput() {
    cin >> input;
}

bool isWin(char c) {
    if ((input[0] == c && input[1] == c && input[2] == c)
        || (input[3] == c && input[4] == c && input[5] == c)
        || (input[6] == c && input[7] == c && input[8] == c)
        || (input[0] == c && input[3] == c && input[6] == c)
        || (input[1] == c && input[4] == c && input[7] == c)
        || (input[2] == c && input[5] == c && input[8] == c)
        || (input[0] == c && input[4] == c && input[8] == c)
        || (input[2] == c && input[4] == c && input[6] == c)
    ) {
        return true;
    }

    return false;
}

bool isFinished() {
    // O가 이겨서 끝난 경우
    if (isWin('O')) {
        return true;
    }

    // X가 이겨서 끝난 경우
    if (isWin('X')) {
        return true;
    }

    // 아무도 승리 확정이 아니며 게임이 진행 중인 경우
    for (int i = 0; i < input.length(); i++) {
        if (input[i] == '.') {
            return false;
        }
    }

    // 이긴 사람은 없지만 끝난 경우
    return true;
}

void solve() {
    // 1. X와 O의 개수 체크해서 invalid 걸러내기
    int xCount = 0;
    int oCount = 0;
    for (char c : input) {
        if (c == 'X') {
            xCount++;
        } else if (c == 'O') {
            oCount++;
        }
    }

    // O가 X보다 많이 나올 수 없다.
    if (oCount > xCount) {
        result = "invalid";
        return;
    }

    // X가 O보다 2개 이상 더 나올 수 없다.
    if (xCount > oCount + 1) {
        result = "invalid";
        return;
    }

    // 2. X가 더 많이 뒀는데 O가 이긴 경우를 체크해서 invalid 걸러내기
    if (xCount == oCount + 1) {
        if (isWin('O')) {
            result = "invalid";
            return;
        }
    }

    // 3. X와 O가 같은 횟수를 뒀는데 X가 이미 승리조건을 달성한 경우를 체크해서 invalid 걸러내기
    if (xCount == oCount) {
        if (isWin('X')) {
            result = "invalid";
            return;
        }
    }

    // 4. 게임이 최종 상태인지 확인하기
    if (isFinished()) {
        result = "valid";
    } else {
        result = "invalid";
    }
}

void printResult() {
    cout << result << "\n";
}

 

코드 설명

크게 코드 설명이 필요할 것 같지는 않다. 다만 isWin() 메서드를 작성할 때 좀 짜증났다(너무 단순노동인 것 같아서). 이를 좀 더 효율적으로 처리할 수 있는 방법 ... 을 고민해봐야 할 것 같다(지금 말고 언젠가, 왜냐면 코딩테스트 중이라고 생각하면 그냥 저 8개의 케이스를 직접 작성하는 게 더 빠를 수도 있을 것 같다).