문제

틱택토는 두 사람이 하는 게임으로 처음에 3x3의 빈칸으로 이루어진 게임판에 선공이 "O", 후공이 "X"를 번갈아가면서 빈칸에 표시하는 게임입니다. 가로, 세로, 대각선으로 3개가 같은 표시가 만들어지면 같은 표시를 만든 사람이 승리하고 게임이 종료되며 9칸이 모두 차서 더 이상 표시를 할 수 없는 경우에는 무승부로 게임이 종료됩니다.

할 일이 없어 한가한 머쓱이는 두 사람이 하는 게임인 틱택토를 다음과 같이 혼자서 하려고 합니다.

• 혼자서 선공과 후공을 둘 다 맡는다.
• 틱택토 게임을 시작한 후 "O"와 "X"를 혼자서 번갈아 가면서 표시를 하면서 진행한다.

틱택토는 단순한 규칙으로 게임이 금방 끝나기에 머쓱이는 한 게임이 종료되면 다시 3x3 빈칸을 그린 뒤 다시 게임을 반복했습니다. 그렇게 틱택토 수 십 판을 했더니 머쓱이는 게임 도중에 다음과 같이 규칙을 어기는 실수를 했을 수도 있습니다.

• "O"를 표시할 차례인데 "X"를 표시하거나 반대로 "X"를 표시할 차례인데 "O"를 표시한다.
• 선공이나 후공이 승리해서 게임이 종료되었음에도 그 게임을 진행한다.

게임 도중 게임판을 본 어느 순간 머쓱이는 본인이 실수를 했는지 의문이 생겼습니다. 혼자서 틱택토를 했기에 게임하는 과정을 지켜본 사람이 없어 이를 알 수는 없습니다. 그러나 게임판만 봤을 때 실제로 틱택토 규칙을 지켜서 진행했을 때 나올 수 있는 상황인지는 판단할 수 있을 것 같고 문제가 없다면 게임을 이어서 하려고 합니다.

머쓱이가 혼자서 게임을 진행하다 의문이 생긴 틱택토 게임판의 정보를 담고 있는 문자열 배열 board가 매개변수로 주어질 때, 이 게임판이 규칙을 지켜서 틱택토를 진행했을 때 나올 수 있는 게임 상황이면 1을 아니라면 0을 return 하는 solution 함수를 작성해 주세요.

풀이

틀린 아이디어

다음과 같은 조건에 따라서 1과 0을 리턴해주었다.

0. .의 개수 == 9 => return 1
1. X의 개수 > O의 개수 => return 0
2. O의 개수 > X의 개수 + 1 => return 0
3. 빙고의 개수 > 1 => return 0

하지만 반례는 다음과 같았다.
마지막에 O가 정가운데 두면서 빙고가 한꺼번에 두 개가 생기지만 정상적인 플레이가 나올 수 있었다.
OXO
XOX
OXO

아무래도 빙고의 개수만으로는 판단하기 어려울 것 같다.

정답 아이디어

빙고의 개수만으로 판단하기 어렵기 때문에 다음과 같은 조건으로 바꾸어 보았다.

1. 선공(O)이 이긴다면 무조건 O의 개수 == X의 개수 + 1
2. 후공(X)이 이긴다면 무조건 O의 개수 == X의 개수
3. 선공과 후공이 동시에 이길 수 없음.

def won(board, t):
    # 가로줄 판단.
    for row in board:
        if row == [t, t, t]:
            return True
        
    # 세로줄 판단.
    for col in range(3):
        if [board[row][col] for row in range(3)] == [t, t, t]:
            return True
        
    # 대각선 판단.
    if [board[0][0], board[1][1], board[2][2]] == [t, t, t]:
        return True
    if [board[2][0], board[1][1], board[0][2]] == [t, t, t]:
        return True
    
    return False
        
def solution(board):
    board = [list(row) for row in board]
    
    # O의 개수가 X의 개수보다 같거나 1 많아야 함.
    o_count, x_count = 0, 0
    for row in board:
        for c in row:
            if c == 'O':
                o_count += 1
            if c == 'X':
                x_count += 1

    if not (o_count == x_count or o_count == x_count + 1):
        return 0

    # O 혹은 X만 승리조건을 만족해야 함.
    if won(board, 'O') and won(board, 'X'):
        return 0
    
    # O가 승리했다면 o_count == x_count + 1이어야 함.
    if won(board, 'O') and o_count != x_count + 1:
        return 0
    
    # X가 승리했다면 o_count == x_count 여야 함.
    if won(board, 'X') and o_count != x_count:
        return 0

    return 1

C++ 코드

#include <string>
#include <vector>
#include <map>
#include <iostream>

using namespace std;
map<char, int> counter;
map<char, int> bingo_cnt;

int checkBingo(vector<string> board) {
   int bingonum = 0;
   //가로 검사
   for(int i=0; i<3; i++) {
       char ch = board[i][0];
       if(ch == '.') {
           continue;
       }
       for(int j=1; j<3; j++) {
           if(ch != board[i][j]) {
               break;
           }
           if(j == 2) {
               bingonum += 1;
               if (ch == 'O') {
                   bingo_cnt['O'] += 1;
               } else {
                   bingo_cnt['X'] += 1;
               }
           }
       }
   }
   
   //세로 검사
   for(int col=0; col<3; col++) {
       char ch = board[0][col];
       if(ch == '.') {
           continue;
       }
       for(int row=1; row<3; row++) {
           if(ch != board[row][col]) {
               break;
           }
           if(row == 2) {
               bingonum += 1;
               if (ch == 'O') {
                   bingo_cnt['O'] += 1;
               } else {
                   bingo_cnt['X'] += 1;
               }
           }
       }
   }
   
   //우하향 대각선 검사
   char start = board[0][0];
   if(start == board[1][1]) {
       if(start == board[2][2]) {
           bingonum += 1;
           if (start == 'O') {
               bingo_cnt['O'] += 1;
           } else {
               bingo_cnt['X'] += 1;
           }
       }
   }
   
   //좌하향 대각선 검사
   start = board[0][2];
   if(start == board[1][1]) {
       if(start == board[2][0]) {
           bingonum += 1;
           if (start == 'O') {
               bingo_cnt['O'] += 1;
           } else {
               bingo_cnt['X'] += 1;
           }
       }
   }
   
   return bingonum;
}
//규칙1) 무조건 선공(O)개수 >= 후공(X)개수
//규칙2) 선공(O)개수는 후공(X)개수보다 2개 이상 많을 수 없음
//규칙3) 아직 시작 안 한 판일 수도 있음.
int solution(vector<string> board) {
   //규칙1, 2 검사 (개수관련)
   for(int i=0; i<3; i++) {
       for(int j=0; j<3; j++) {
           if(board[i][j] == 'O') {
               counter['O'] += 1;
           } else if (board[i][j] == 'X') {
               counter['X'] += 1;
           } else {
               counter['.'] += 1;
           }
       }
   }
   checkBingo(board);
   for(const auto& [key, value] : bingo_cnt) {
       cout << key << ": " << value << endl;
   }
   
   //O의 개수는 X의개수보다 최대 1개만 많음.
   int diff = counter['O'] - counter['X'];
   if(diff >= 2 or diff < 0) {
       return 0;
   }
   
   //O의 빙고와 X의 빙고가 공존할 수 없음. (둘 다 이길 수 없음)
   if(bingo_cnt['O'] >= 1 and bingo_cnt['X'] >= 1) {
       return 0;
   }
   //X의 빙고가 있으면 O와 X의 개수는 같아야함.
   if(bingo_cnt['X'] >= 1 and !(counter['O'] == counter['X'])) {
       return 0;
   }
   //O가 승리했다면 X의 개수보다 무조건 1개만 많아야함
   if(bingo_cnt['O'] >= 1 and diff != 1) {
       return 0;
   }
   
   return 1;
}