[LeetCode] 794. Valid Tic-Tac-Toe State

3x3 틱택토 보드가 주어질 때, 정상적인 게임 진행으로 도달 가능한 상태인지 판별하는 문제입니다.

접근

보드를 "어떻게 만들어지는지" 시뮬레이션할 필요는 없습니다. 유효한 보드가 반드시 만족해야 하는 불변식(invariant) 만 확인하면 됩니다.

핵심은 두 가지입니다.

1. 개수 규칙: X가 먼저 두므로 xCount === oCount 또는 xCount === oCount + 1
2. 승리 규칙: 누군가 이기면 게임이 끝나므로 그 이후 수는 놓일 수 없음
   • X가 이겼다면 마지막 수가 X이므로 xCount === oCount + 1
   • O가 이겼다면 마지막 수가 O이므로 xCount === oCount

이 두 조건이 모두 통과하면 유효한 보드입니다.

풀이

function validTicTacToe(board: string[]): boolean {
  let oCount = 0;
  let xCount = 0;
  for (let i = 0; i < 3; i++) {
    for (let j = 0; j < 3; j++) {
      switch (board[i][j]) {
        case 'O':
          oCount++;
          break;
        case 'X':
          xCount++;
          break;
      }
    }
  }

  const isPlayerWin = (player: 'X' | 'O') => {
    const playerSign = player.repeat(3);
    const rows = [...board];
    const cols = board.reduce(
      (acc, cur) => [acc[0] + cur[0], acc[1] + cur[1], acc[2] + cur[2]],
      ['', '', ''],
    );
    const diagonals = ['', ''];
    for (let i = 0; i < 3; i++) {
      diagonals[0] += board[i][i];
      diagonals[1] += board[i][2 - i];
    }
    return rows.includes(playerSign) || cols.includes(playerSign) || diagonals.includes(playerSign);
  };

  if (oCount > xCount) return false;
  if (xCount - oCount > 1) return false;
  if (isPlayerWin('X') && xCount !== oCount + 1) return false;
  if (isPlayerWin('O') && oCount !== xCount) return false;
  return true;
}

승리 판정은 문자열로 처리했습니다. 행은 board의 각 원소가 그대로 한 줄이고, 열은 reduce로 세로 방향 문자를 이어 붙여 만들고, 대각선 두 개는 인덱스 [i][i]와 [i][2 - i]로 모읍니다. 8개 라인 중 "XXX" 또는 "OOO"가 있는지만 보면 됩니다.

정리하면서 깨달은 점

처음에는 "X와 O가 동시에 이길 수 없다"는 조건을 따로 넣었는데, 빼도 통과합니다.

• X 승리 → xCount === oCount + 1
• O 승리 → xCount === oCount

두 식은 동시에 성립할 수 없으므로, 아래 두 줄이 이미 그 경우를 걸러냅니다. 조건을 나열하기 전에 서로 포함 관계가 있는지 확인해 볼 만합니다.

Math.abs(oCount - xCount) > 1 도 마찬가지입니다. 바로 위에서 oCount > xCount를 이미 걸렀으니 xCount - oCount > 1로 충분합니다.

복잡도

보드 크기가 3x3으로 고정이라 O(1) 입니다.