문제 풀이 과정을 공유하고자 한다.
문제 출처

1. 문제설명

  • 틱택토 게임
    • 3x3 고정 크기의 보드판이 주어진다.
    • 선공 O, 후공 X, 빈칸 .
    • 가로, 세로, 대각선 방향으로 3개가 같은 표시라면 승리
  • 해당 게임이 나올 수 있는 상황이라면 1, 아니라면 0 출력



2. 알고리즘 설계

  • 처음엔 BFS로 경로를 탐색하면서 정상적으로(?) 이뤄진 게임인지 탐색해야 하는 줄 알았다.
  • 그러나 문제를 보면 나올 수 있는 경우의 수라면 1이 된다고 되어 있다.
  • 예시
    • 이 경우는 나올 수 있으므로, 1이다.
    O O O
. . .
X X
    • 실제로 플레이 했다면, O가 두칸을 차지했을 때 다음과 같이 막았을 것이다.
      • 이런 건 전혀 고려하지 않아도 된다.
    O O X
. . .
  • 문제를 보면, “실수를 했을 가능성이 있는가”를 묻는 게 아닌 “이 게임판이 규칙을 지켜서 진행한 틱택토에서 나올 수 있는 상황인가”를 묻는 문제라는 것에 유의해주세요.



3. 로직

  • 편의상 O는 선공, X는 후공으로 표현
  • 나올 수 없는 경우의 수 전부 체크
    • 선공의 개수가 후공의 개수보다 적거나, 선공의 개수 - 후공의 개수가 1보다 큰 경우
    • 선공, 후공이 둘다 이기는 경우
    • 선공이 이겼는데, 선공과 후공의 개수가 1이 아닌 경우
    • 후공이 이겼는데, 선공과 후공의 개수가 같지 않은 경우


4. 전체 코드

#include <string>
#include <vector>

using namespace std;

// 승리할 수 있는 모든 경우의 수
bool check(vector<string> board, char c) 
{
    for(int i=0; i<3; i++) {
        if (board[i][0] == c && board[i][1] == c && board[i][2] == c)
            return true;
        if (board[0][i] == c && board[1][i] == c && board[2][i] == c)
            return true;
    }
    
    if (board[0][0] == c && board[1][1] == c && board[2][2] == c)
        return true;
    if (board[0][2] == c && board[1][1] == c && board[2][0] == c)
        return true;
    
    return false;
}

int solution(vector<string> board) {
    int f_cnt=0, s_cnt=0;
    for(string s : board) {  // 선공, 후공 개수 세기
        for(char c : s) {
            if(c == 'O')
                f_cnt++;
            else if(c == 'X')
                s_cnt++;
        }
    }
    
	// case 1
    if(f_cnt < s_cnt || 1 < f_cnt - s_cnt)
        return 0;
    
    bool f_sign = check(board, 'O');
    bool s_sign = check(board, 'X');
    
    if(f_sign && s_sign) return 0;  // case 2
    if(f_sign && f_cnt-s_cnt != 1) return 0;  // case 3
    if(s_sign && f_cnt != s_cnt) return 0;  // case 4
    
    return 1;
}


5. 소감

  • 보드판의 크기가 3x3이라서, 승리 경우의 수가 단순했다.
  • 만약 좀 더 큰 보드판이거나, 정방 보드판(NxN)이 아니었다면..?