미니맥스 틱택토

문제

미니맥스는 게임 프로그램이 수를 고르는 방법입니다. 두 플레이어가 모두 완벽하게 둔다고 가정하고, 끝난 모든 게임에 점수를 매긴 뒤 그 점수를 게임 트리 위로 올려 보냅니다. 차례인 플레이어는 자신에게 점수가 가장 높은 자식을 고릅니다.

보드는 행 순서로 읽는 9글자 문자열 (인덱스 0-8)이며, "X", "O" 또는 빈칸을 뜻하는 "."로 이루어집니다. X가 항상 먼저 두므로 두 사람의 표시 수가 같으면 X 차례이고, 그렇지 않으면 O 차례입니다.

끝난 게임의 점수는 차례인 플레이어의 관점에서 승리 +1, 무승부 0, 패배 -1입니다. 미니맥스 점수가 가장 좋은 빈칸을 반환하고, 똑같이 좋은 칸이 여러 개면 가장 작은 인덱스를 반환합니다.

best_move(board)를 구현하세요.

board: 아직 아무도 이기지 않았고 빈칸이 하나 이상 있는 올바른 국면.

최선의 수의 인덱스 (0-8)를 반환합니다.

board는 정확히 9글자이며, 각 글자는 X, O 또는 .

실제 게임에서 나올 수 있는 국면이며, 아무도 이기지 않았고 빈칸이 하나 이상 있습니다

예시 1

입력:
board = "XX.OO...."

예상 출력:
expected = 2

입력:
std::string board = "XX.OO....";

예상 출력:
long long expected = 2;

입력:
string board = "XX.OO....";

예상 출력:
long expected = 2;

X와 O가 두 개씩이므로 X 차례입니다. 2에 두면 맨 윗줄이 완성되어 바로 이깁니다 (+1).

예시 2

입력:
board = "X..OO...X"

예상 출력:
expected = 5

입력:
std::string board = "X..OO...X";

예상 출력:
long long expected = 5;

입력:
string board = "X..OO...X";

예상 출력:
long expected = 5;

X 차례입니다. O가 5에서 가운데 줄을 완성하려 합니다. 다른 수는 모두 O가 이기게 되고 (-1), 5를 막으면 무승부 (0)가 되므로 답은 5입니다.

먼저 스스로 풀어 본 뒤 힌트를 하나씩 열어 보세요.

힌트 1

X와 O의 개수로 누구 차례인지 판단한 뒤, 가능한 모든 move를 재귀적으로 평가하세요.

힌트 2

terminal board는 현재 player 관점에서 점수를 매기고, 그 값을 최대화하는 move를 고르세요.

힌트 3

여러 move가 동점이면 가장 먼저 나온 빈 cell index를 유지하고, 추가 move를 보기 전에 win을 먼저 판정하세요.

예상 복잡도

시간 O(9!), 추가 공간 O(9)

이 문제는 CodeUtility에 맞게 수정되었습니다. 위의 설명과 제한 조건을 따르세요.