27900번 - 4차 산업 혁명 2 점수언어 제한함수 구현

《Connect Four》는 $6$행 $7$열의 수직으로 세워진 직사각형 게임판에서 진행하는 게임입니다. 두 플레이어가 번갈아가며 턴을 진행하며, 각 턴에 플레이어는 아직 채워지지 않은 칸이 있는 열을 하나 골라 자신의 말을 떨어뜨립니다. 떨어뜨린 말은 채워지지 않은 가장 아래쪽 칸에 들어갑니다. 먼저 자신의 말 네 개를 가로, 세로, 또는 대각선으로 한 줄을 이루도록 하는 플레이어가 승리합니다. 편의상 먼저 말을 놓는 플레이어의 말을 빨간색, 상대편의 말을 노란색이라 하겠습니다. 또한 열 번호는 가장 왼쪽에 있는 열에서 시작하여 오른쪽으로 가면서 $1$번부터 $7$번까지 붙입니다.

여러분은 현존하는 최강의 Connect Four 인공지능을 상대로 승리해야 합니다. 여러분이 먼저 플레이합니다.

최선의 수는 다음과 같이 (게임 상태에 대해 재귀적으로) 정의합니다.

• 이길 수 있다면, 두 플레이어가 최선의 수를 둘 때 내가 이기면서 말을 최대한 적게 놓게 되는 수가 최선의 수입니다.
• 이길 수는 없지만 비길 수 있다면, 두 플레이어가 최선의 수를 둘 때 비기는 수가 최선의 수입니다.
• 이길 수도 없고 비길 수도 없다면, 두 플레이어가 최선의 수를 둘 때 (내가 지면서) 말을 최대한 많이 놓게 되는 수가 최선의 수입니다.

이 문제에서는 게임판을 길이가 $14$인 문자열로 인코딩합니다. 먼저 각 열을 다음과 같이 인코딩합니다.

• $x = 1$로 초기화합니다.
• 놓여있는 말을 위에서부터 하나씩 읽습니다. 빨간색 말이라면 $2x$가, 노란색 말이라면 $2x+1$이 새로운 $x$가 됩니다.
• 모두 읽은 다음 $x$의 값을 $16$진수로 씁니다. 한 자리 수인 경우 앞에 $0$을 붙입니다. (ex. $x=13$이면 0d, $x=127$이면 7f)

간단하게 설명하자면, 열을 위에서부터 순서대로 읽고, 노란색 말을 $1$, 빨간색 말을 $0$으로 치환한 다음, 맨 왼쪽에 $1$을 추가한 이진수를 $16$진수로 쓰면 됩니다.

다음으로 게임판의 $1$열부터 $7$열까지를 인코딩한 문자열을 순서대로 이어 붙여 하나의 문자열을 만듭니다. 이 문자열이 게임판의 상태를 인코딩한 결과입니다. 아래는 인코딩한 결과가 각각 01010102010101, 0305146a032501, 55656a6a2c5555인 게임판을 나타낸 그림입니다.

플레이어의 플레이는 말을 떨어뜨릴 열의 번호로 나타낼 수 있습니다. 예를 들어 $4$, $5$, $3$, $2$, $4$, $4$, $1$, $7$ 순서로 플레이한 뒤의 게임판은 다음과 같으며, 이 게임판을 인코딩한 문자열은 0203020c030103입니다.

여러분은 아래 함수들을 구현해야 합니다.

void init()

• 이 함수는 단 한 번, 다른 모든 next_move() 함수가 호출되기 전에 호출됩니다.

int next_move(std::string state)

• state: 위에서 설명한 방법대로 현재 판의 상태가 인코딩된 문자열
• 이 함수는 판의 상태에 따라 다음 플레이, 즉 말을 떨어뜨릴 열을 반환해야 합니다. 열 번호는 $1$부터 시작합니다.
• 이 함수의 반환값은 $0$ 이상 $7$ 이하여야 합니다.
• 반환값이 $0$인 경우, 해당 상태에서는 게임을 더 이상 진행하지 않고 패배합니다.
• 이 함수는 테스트 케이스당 최대 $21$번 호출됩니다.

이 문제에는 $10$개의 테스트 케이스가 있습니다. 각 테스트 케이스마다 여러분은 항상 최선의 수 중 하나를 두는 인공지능과 대결합니다. 채점기는 다음과 같이 동작합니다.

1. 처음 게임판을 인코딩한 문자열인 "01010101010101"을 next_move() 함수의 state 인자로 넘겨줍니다.
2. next_move() 함수의 반환값을 확인합니다. 만약 반환값이 state에 대한 최선의 수가 아니거나 $0$이라면 게임을 더 이상 진행하지 않습니다. 그렇지 않다면 반환값과 state를 바탕으로 새로운 게임판을 만듭니다.
3. 만약 새로운 게임판에서 당신의 말 네 개가 가로, 세로, 또는 대각선으로 한 줄을 이루고 있다면 당신의 승리로 프로그램을 종료합니다. 그렇지 않다면 그 상태에서 인공지능이 최선의 수를 둔 후의 게임판을 인코딩한 문자열을 다시 next_move() 함수의 state 인자로 넘겨줍니다.

하나의 테스트 케이스에서 채점기는 항상 정해진 대로 동작합니다. 다시 말해서, 3번 과정에서 만약 최선의 수가 여러 개일 때 인공지능이 선택하는 최선의 수는, 해당 테스트 케이스의 채점 과정에서 도달할 수 있는 모든 게임판에 대해 정해져 있습니다. 인공지능의 선택은 각 테스트 케이스마다 다를 수 있습니다.

각 테스트 케이스마다, 만약 당신이 게임을 이겼다면 $2790$점을 받습���다. 그렇지 않고 만약 당신의 next_move() 함수가 $0$ 이상 $7$ 이하의 정수가 아닌 값을 반환했다면 $0$점을 받습니다. 그렇지 않다면 당신의 next_move() 함수가 최선의 수를 반환한 횟수를 $n$이라 할 때, 이 테스트 케이스에 대한 여러분의 점수는 다음 표와 같습니다.

모든 테스트 케이스에서 채점 프로그램이 시간 내에 정상적으로 종료했을 경우에 한해, 각 테스트 케이스의 점수의 합이 여러분의 점수가 됩니다. 예를 들어, 모든 테스트 케이스에서 $n = 3$인 경우 $40$점을 받습니다.

Sample grader는 인터랙티브하게 동작합니다. Sample grader의 동작을 위해서는 당신의 next_move() 함수의 반환값이 최선의 수인지 판단하고, 인공지능이 선택할 최선의 수를 직접 입력해야 합니다.

• 만약 next_move() 함수의 반환값대로 게임을 진행했을 때 게임이 끝났다면 $0$을 입력해야 합니다.
• 만약 next_move() 함수의 반환값이 최선의 수가 아니라면 $-1$을 입력해야 합니다.
• 이외의 경우 인공지능이 선택할 최선의 수를 입력해야 합니다.

다음은 Sample grader의 동작 예시입니다.

Sample grader는 실제 채점에서 사용하는 그레이더와 다를 수 있습니다. 또한, 위 예시의 input은 실제 인공지능의 최선의 수가 아닐 수 있습니다.

sample_grader.cpp