본문으로 건너뛰기

1. 문제 분석​

1.1 핵심 요구사항​

  • 3x3 틱택토 게임판의 상태가 주어질 때, 해당 상태가 규칙을 지켜서 나올 수 있는 상황인지 판단
  • 규칙 위반 사항:
    • 순서 위반 (O 차례에 X를 두거나 그 반대)
    • 게임이 끝난 후에도 계속 진행
  • 유효한 상태면 1, 아니면 0을 반환

1.2 접근 방법 검토​

  1. 완전탐색(DFS/백트래킹) 접근
    • 가능한 모든 게임 진행 상태를 생성하여 비교
    • 장점: 모든 케이스를 커버할 수 있음
    • 단점: 시간/공간 복잡도가 매우 높음
  2. 상태 검증 접근
    • O와 X의 개수 관계 검증
    • 승리 조건 검증
    • 장점: 빠른 실행 시간, 적은 메모리 사용
    • 단점: 모든 예외 케이스를 고려해야 함

1.3 시간 복잡도 분석​

  1. 완전탐색 접근
    • 시간 복잡도: O(9!)
    • 공간 복잡도: O(9! * 9)
    • 9!가지의 게임 진행 순서를 모두 검사
  2. 상태 검증 접근
    • 시간 복잡도: O(1)
    • 공간 복잡도: O(1)
    • 고정된 크기(3x3)의 게임판만 검사
팁

상태 검증 접근이 가장 효율적입니다. 게임판 크기가 3x3으로 고정되어 있고, 간단한 규칙으로 유효성을 판단할 수 있기 때문입니다.

2. 문제 풀이​

2.1 풀이 전략​

  1. O와 X의 개수 관계 확인
    • O의 개수는 X의 개수와 같거나 하나 더 많아야 함
  2. 승리 조건 검증
    • O가 이겼을 때는 O가 X보다 하나 더 많아야 함
    • X가 이겼을 때는 O와 X의 개수가 같아야 함
    • O와 X가 동시에 이길 수 없음

2.2 구현 코드​

class Solution {
    public int solution(String[] board) {
        // 게임판 상태 카운트
        int countO = 0;
        int countX = 0;
        
        // O와 X 개수 세기
        for (String row : board) {
            for (char cell : row.toCharArray()) {
                if (cell == 'O') countO++;
                if (cell == 'X') countX++;
            }
        }
        
        // 기본 규칙 검증: O는 X보다 같거나 하나 많아야 함
        if (countX > countO || countO > countX + 1) {
            return 0;
        }
        
        // 승리 조건 검증
        boolean oWin = isWinner(board, 'O');
        boolean xWin = isWinner(board, 'X');
        
        // 둘 다 이긴 경우 불가능
        if (oWin && xWin) {
            return 0;
        }
        
        // O가 이겼을 때는 O가 하나 더 많아야 함
        if (oWin && countO != countX + 1) {
            return 0;
        }
        
        // X가 이겼을 때는 개수가 같아야 함
        if (xWin && countO != countX) {
            return 0;
        }
        
        return 1;
    }
    
    private boolean isWinner(String[] board, char player) {
        // 가로 검사
        for (int i = 0; i < 3; i++) {
            if (board[i].charAt(0) == player && 
                board[i].charAt(1) == player && 
                board[i].charAt(2) == player) {
                return true;
            }
        }
        
        // 세로 검사
        for (int i = 0; i < 3; i++) {
            if (board[0].charAt(i) == player && 
                board[1].charAt(i) == player && 
                board[2].charAt(i) == player) {
                return true;
            }
        }
        
        // 대각선 검사
        if (board[0].charAt(0) == player && 
            board[1].charAt(1) == player && 
            board[2].charAt(2) == player) {
            return true;
        }
        
        if (board[0].charAt(2) == player && 
            board[1].charAt(1) == player && 
            board[2].charAt(0) == player) {
            return true;
        }
        
        return false;
    }
}

2.3 코드 설명​

  1. 상태 카운트
    • O와 X의 개수를 세어 기본적인 규칙 위반 여부 확인
    • O는 선공이므로 X보다 같거나 하나 많아야 함
  2. 승리 조건 검증
    • isWinner 메소드로 각 플레이어의 승리 여부 확인
    • 가로, 세로, 대각선 방향으로 3개 연속 확인
    • 승리 조건과 개수 관계가 맞는지 검증
      • O 승리: O가 하나 더 많아야 함
      • X 승리: O와 X가 같아야 함
      • 동시 승리: 불가능
  3. 최적화 포인트
    • 3x3 고정 크기이므로 반복문 대신 직접 인덱스 접근
    • 불필요한 배열 복사나 변환 없이 String 배열 직접 사용
    • 조기 반환으로 불필요한 검증 방지

3. 마치며​

  • 이 문제의 핵심은 게임 규칙을 정확히 이해하고 최소한의 검증으로 유효성을 판단하는 것입니다.
  • 초기에는 복잡한 완전탐색이나 시뮬레이션을 고려할 수 있지만, 실제로는 간단한 규칙 검증만으로도 충분히 해결할 수 있습니다.