버섯 게임

NYPC CODE BATTLE · 온라인 라운드 연습문제

문제 설명

메이플 월드의 평화로운 숲속, 예티와 핑크빈은 오늘도 사이좋게 버섯 밭을 가꾸고 있었습니다.
그러던 어느 날, 버섯마다 숫자가 적혀 있다는 사실을 발견한 두 친구는 이 숫자를 활용해 새로운 게임을 만들기로 했습니다.
그들은 버섯 밭의 일부를 점령하며 경쟁하는 게임을 고안했고, 아래의 규칙에 따라 번갈아 가며 영역을 선택해 나갑니다.

게임 규칙

Rule 1
플레이어는 자신의 턴에 버섯 밭에서 하나의 직사각형 영역을 선택합니다.
Rule 2
선택한 영역 내의 숫자 합이 정확히 $10$ 인 경우, 해당 영역의 버섯은 제거되며 플레이어가 그 영역을 점령합니다.
이때, 영역 안에 상대방이 이미 점령한 칸이 포함되어 있다면 해당 칸의 소유권도 빼앗을 수 있습니다.
또한, 선택한 직사각형의 네 변에는 각각 최소 하나 이상의 버섯이 영역 안쪽으로 인접해 있어야 합니다.
Rule 3
선택 가능한 영역이 없거나 전략적으로 선택을 하지 않으려 한다면, 선택을 생략하고 턴을 넘길 수 있습니다.
Rule 4
두 플레이어가 연속으로 턴을 넘기면 게임이 종료됩니다.
종료 시점에 더 많은 칸을 점령한 플레이어가 승리합니다.

예티 또는 핑크빈 중 한 명이 되어, 버섯 밭에서 더 많은 칸을 점령할 수 있는 프로그램을 작성하세요.

입/출력 형식

참가자의 프로그램은 한 줄씩 입력을 받아 각 명령에 따라 동작해야 합니다. 출력이 필요한 명령은 아래 표에서 빨간색으로 표시되어 있습니다.

커맨드	입력 형식	설명
READY	`READY (FIRST\|SECOND)`	플레이어의 선공/후공 정보를 알려주는 명령입니다. 입력 준비 완료를 의미하는 `OK` 를 3초 이내에 출력해야 합니다.
INIT	`INIT ...`	게임 보드 정보를 초기화하는 명령입니다. `...`에는 $10$ 개의 문자열이 주어지며, 각 문자열은 $17$ 자리 숫자로 구성되어 있습니다. 각 숫자는 $1$ 이상 $9$ 이하의 정수이며, 해당 위치의 버섯에 적힌 숫자를 의미합니다. 출력은 필요하지 않습니다. 각 숫자는 $1$ 이상 $9$ 이하의 정수가 동일한 확률로 서로 독립적으로 주어집니다.
TIME	`TIME t₁ t₂`	현재까지 각 플레이어의 남은 시간을 알려주는 명령입니다. $t_1$ 은 내 프로그램의 남은 시간이고, $t_2$ 는 상대 프로그램의 남은 시간입니다. 이 명령을 받으면, 플레이어가 이번 턴에 선택할 직사각형의 좌표를 $r_1$ $c_1$ $r_2$ $c_2$ 형식으로 출력해야 합니다. 게임 보드의 왼쪽 위 좌표는 $(r, c) = (0, 0)$ 이고, 오른쪽 아래 좌표는 $(9, 16)$ 입니다. 패스할 경우 $r_1 = c_1 = r_2 = c_2 = -1$ 을 출력하며, 출력 값은 다음 조건을 만족해야 합니다. $-1 \le r_1 \le r_2 \le 9$ $-1 \le c_1 \le c_2 \le 16$ 처음 $t_1, t_2$ 로 주어지는 시간은 `READY` 명령어에 사용한 시간과 관련 없이 $10\,000$ 입니다.
OPP	`OPP x₁ y₁ x₂ y₂ t`	상대방의 선택 정보를 알려주는 명령입니다. 상대방이 선택한 직사각형 좌표 $r_1$ $c_1$ $r_2$ $c_2$ 와 해당 턴에 사용한 시간 $t$ 가 주어집니다. 상대가 패스한 경우에는 $r_1 = c_1 = r_2 = c_2 = -1$ 이 주어집니다. 출력은 필요하지 않습니다.
FINISH	`FINISH`	게임 종료를 알리는 명령입니다. 이 명령을 받으면 프로그램은 정상적으로 종료되어야 하며, 출력은 필요하지 않습니다.

모든 출력 이후에는 버퍼를 flush해야 합니다. 버퍼를 flush하지 않은 경우 출력이 제대로 되지 않아 TLE가 발생할 수 있습니다. 언어별로 버퍼를 flush하는 방법에 대해서는 각 언어의 공식 레퍼런스 문서와 예제 코드를 참고해 주세요.

예제 코드

다음은 각 언어별로 작성한 예제 코드입니다.

C20: sample_code.c
C++20: sample_code.cpp
C#: Main.cs
OpenJDK Java 21: Main.java
Node.js: sample_code.js
Typescript: sample_code.ts
PyPy3 / Python3: sample_code.py
Rust 2024: sample_code.rs
Lua: sample_code.lua
Go: sample_code.go
Kotlin: sample_code.kt

예제 코드는 올바른 조건의 직사각형 중 $(r_1, c_1, r_2, c_2)$ 가 사전순으로 가장 작은, 즉 가능한 가장 왼쪽 위의 직사각형을 골라서 출력합니다. 선택 가능한 직사각형이 없을 경우에는 턴을 넘깁니다.

샘플 AI와의 대결

제출된 코드가 컴파일에 성공하면, 총 7개의 샘플 AI와 대결을 진행하게 됩니다.
각 샘플 AI와는 선공/후공을 번갈아 가며 2번의 대결을 치릅니다. 승패에 따른 점수는 다음과 같습니다.

승리: +1승
무승부: +0.5승
패배: +0승

샘플 AI의 전략은 아래와 같습니다.

배틀 번호	설명
1 / 2	자기의 턴에 항상 "패스"만 합니다.
3 / 4	제공된 예제 코드와 같은 동작을 수행합니다.
5 / 6	게임 시뮬레이터 샘플 AI 핑크빈의 전략을 사용합니다.
7 / 8	중간 난이도의 방어형 전략을 사용합니다.
9 / 10	중간 난이도의 공격형 전략을 사용합니다.
11 / 12	어려운 난이도의 방어형 전략을 사용합니다.
13 / 14	어려운 난이도의 공격형 전략을 사용합니다.

시각화 도구 (샘플 AI / 번갈아 플레이하기 / 로그 분석)

게임을 샘플 AI와 플레이, 두 명이 번갈아가면서 플레이 해 볼 수 있고, 게임의 시뮬레이터 및 테스팅 툴이 출력한 로그를 시각화하는 시각화 도구를 사용할 수 있습니다.

샘플 AI의 대결에서 각 배틀의 로그 파일을 다운받을 수 있습니다. 로그 시각화 도구를 활용하여 게임이 어떻게 진행되었는지 살펴보고 전략을 수정하세요.

테스팅 툴 (GUI)

참가자가 작성한 프로그램을 테스팅하기 위한 테스팅 툴인 testing-tool-mushroom이 제공됩니다. 참가자의 환경에서 컴파일한 실행 파일 혹은 참가자의 실행 환경의 python, java, node, lua 환경과 스크립트를 이용하여 로컬에서 문제를 테스트해 볼 수 있습니다.

64비트 Windows (x86-64) (다운로드)
- 다운받은 .exe 파일을 실행합니다.
MacOS Universal (다운로드)
- .dmg 파일을 더블 클릭한 이후 testing-tool-mushroom 파일을 Applications 폴더에 드래그해서 복사합니다. 그 이후 testing-tool-mushroom 앱을 실행합니다.
- "개발자를 확인할 수 없기 때문에 'testing-tool-mushroom-app'을(를) 열 수 없습니다." 라는 안내가 나오는 경우, "설정 > 개인정보 및 보안"에서 앱의 정보를 확인합니다.
64비트 Ubuntu (AMD64) (다운로드)
- apt 혹은 dpkg을 이용해 .deb 파일을 설치한 이후 testing-tool-mushroom을 실행합니다.
64비트 RedHat (x86-64) (다운로드)
- rpm 혹은 yum을 이용해 .rpm 파일을 설치한 이후 testing-tool-mushroom을 실행합니다.

테스팅 툴 (커맨드라인, 파이썬 스크립트)

참가자가 작성한 프로그램을 테스팅하기 위한 테스팅 툴인 testing_tool.py (다운로드) 가 주어집니다. 테스팅 툴은 Python 3.12로 작성된 프로그램입니다. 이 프로그램의 실행에 관해서는 [파이썬 설정 및 사용법]을 참고하세요.

테스팅 툴을 사용하기 위해서는 testing_tool.py 와 같은 위치에 setting.ini를 작성합니다. 내용은 다음과 같습니다.

INPUT=<입력 파일 경로>
LOG=<로그 파일 경로>
EXEC1=<선공 유저의 프로그램 실행 커맨드>
EXEC2=<후공 유저의 프로그램 실행 커맨드>

예를 들어, 같은 폴더에 있는 input.txt를 입력으로, 로그를 log.txt에 출력하고, 선공 유저의 프로그램 실행 커맨드를 ./Main.exe, 후공 유저의 프로그램 실행 커맨드를 python3 main.py --test라고 하면, 다음과 같이 작성합니다.

INPUT=./input.txt
LOG=./log.txt
EXEC1=./Main.exe
EXEC2=python3 main.py --test

테스팅 툴 입력 형식 및 로그 해석

테스팅 툴의 입력 파일은 보드의 초기 상태를 나타냅니다. 보드는 $10$ 개의 줄로 이루어져있어야 하며, 각 줄은 $17$ 개의 $1$ 이상 $9$ 이하의 숫자로 이루어져야 합니다. 이후 testing_tool.py를 실행합니다. 실행한 이후에는 로그 파일로 지정한 ./log.txt에 로그가 출력됩니다.

로그는 다음과 같은 정보를 출력합니다.

INIT <s₁> <s₂> ... <s₁₀>
- 게임을 시작할 때 보드의 i번째 줄이 <sᵢ>임을 의미합니다.
<FIRST/SECOND> <r₁> <c₁> <r₂> <c₂> <time>
- 선공 (FIRST) 혹은 후공 (SECOND)이 <r₁>행 <c₁>열부터 <r₂>행 <c₂>열까지 선택했고, <time>밀리초를 사용했다는 것을 의미합니다.
FINISH
- 게임의 정상적인 종료를 나타냅니다.
SCORE<FIRST/SECOND> <score>
- 선공 (FIRST) 혹은 후공 (SECOND)이 받은 점수가 <score>임을 나타냅니다.
ABORT <0/1> <reason>
- 선공 (0) 혹은 후공 (1)이 <reason>을 이유로 프로그램이 비정상종료했음을 의미합니다.

testing_tool.py를 수정하는 것은 자유이지만, 수정된 testing_tool.py 혹은 테스팅 툴의 로그 파일 등을 팀원 이외의 사람과 공유하거나, 이와 관해 토론해서는 안됩니다.

채점 결과에서는 테스팅 툴이 출력한 로그와 같은 형식의 실행 로그를 받아볼 수 있습니다. 단, 실제 채점 프로그램은 테스팅 툴과 다르게 구현되어있으므로, 테스팅 툴에서의 작동이 채점 서버에서의 정상 작동을 의미하지는 않습니다.

예시

예시 입력 (테스팅 툴에 사용됨)

52466443835422223
13254826938785712
87598398564241564
72722154162442227
43968227685821641
27727492381231148
56138649164249527
36281415328768234
62682694189422313
62269566965435457

예시 인터랙션

아래의 INIT ...로 쓰인 문자열은 보드의 입력을 나타내며, 다음과 같이 주어집니다.

INIT 52466443835422223 13254826938785712 87598398564241564 72722154162442227 43968227685821641 27727492381231148 56138649164249527 36281415328768234 62682694189422313 62269566965435457

선공 입력	선공 출력	후공 입력	후공 출력	로그
`READY FIRST`		`READY SECOND`
	`OK`		`OK`
`INIT ...`		`INIT ...`		`INIT ...`
`TIME 10000 10000`
(70ms 소요)	`0 11 0 14`
		`OPP 0 11 0 14 70`		`FIRST 0 11 0 14 70`
		`TIME 10000 9930`
		(40ms 소요)	`1 13 5 13`
`OPP 1 13 5 13 40`				`SECOND 1 13 5 13 40`
`TIME 9930 9960`
(20ms 소요)	`-1 -1 -1 -1`
		`OPP -1 -1 -1 -1 20`		`FIRST -1 -1 -1 -1 20`
		`TIME 9960 9910`
		(10ms 소요)	`-1 -1 -1 -1`
`OPP -1 -1 -1 -1 10`				`SECOND -1 -1 -1 -1 10`
`FINISH`	(프로그램 종료)	`FINISH`	(프로그램 종료)	`FINISH`
				`SCOREFIRST 4`
				`SCORESECOND 5`