Connexion

문제 설명

버섯의 성에 도착한 예티와 핑크빈은 다양한 색과 문양의 버섯을 보게 되었습니다. 예티는 버섯을 같은 모양끼리 핑크빈은 버섯을 같은 색끼리 모으고 싶어했습니다.

게임 규칙

Connexion은 $2$ 명이서 플레이하는 턴제 게임입니다. 게임은 $2$ 명이서 게임 보드와 게임 타일을 사용하여 진행합니다. 게임은 준비 단계, 배치 단계, 점수 계산 단계로 이루어집니다.

게임 보드

게임 보드는 위와 같은 모양으로, 총 $64$ 개의 칸으로 이루어져 있습니다. 각 보드의 좌표는 (열, 행, 부호)의 순서쌍으로 나타낼 수 있습니다.

열은 왼쪽에서 오른쪽으로 a, b, c, d, e, f 총 $6$ 개가 있습니다.
행은 아래에서 위쪽으로 1, 2, 3, 4, 5, 6 총 $6$ 개가 있습니다.
각 열과 각 행이 만나는 곳에는 두 개의 칸 -와 +이 있습니다.

칸을 표현할 때는 열을 나타내는 문자, 행을 나타내는 문자와 부호, 총 $3$ 개의 문자를 차례로 붙여서 나타냅니다.

열, 행, 부호의 가능한 $72$ 개 조합 중, 다음 $8$ 개는 사용하지 않습니다.

a1-, a4-, c3+, c6+, d1-, d4-, f3+, f6+

각 칸은 다음과 같은 방법으로 연결되어 있습니다.

-칸은 (존재하는 경우) 다음 세 칸과 연결되어 있습니다.
- 같은 열, 같은 행의 +,
- 바로 왼쪽 열, 같은 행의 +,
- 같은 열, 바로 아랫쪽 행의 +.
+칸은 (존재하는 경우) 다음 세 칸과 연결되어 있습니다.
- 같은 열, 같은 행의 -,
- 바로 오른쪽 열, 같은 행의 -,
- 같은 열, 바로 위쪽 행의 -.

예를 들어, c5-은 c5+, b5+, c4+과 연결되어 있고, f4+은 f4-, f5-와 연결되어 있습니다.

게임 타일

Connexion의 게임 타일에는 색과 문양이 있습니다. 색은 R ( 빨간색 타일 ), G ( 초록색 타일 ), B ( 파란색 타일 ), Y ( 노란색 타일 )의 $4$ 종류가 있으며, 문양은 1 ( 1번 문양 ), 2 ( 2번 문양 ), 3 ( 3번 문양 ), 4 ( 4번 문양 )의 $4$ 종류가 있습니다. 색과 문양의 서로 다른 $16$ 가지 조합에 대해, 해당 조합의 타일이 $4$ 개씩, 총 $64$ 개가 있습니다. 타일은 색을 표현하는 문자와 문양을 표현하는 문자, 총 $2$ 개의 문자를 차례로 붙여서 나타냅니다.

준비 단계

선공과 후공을 정합니다. 각 사람은 색과 문양의 서로 다른 $16$ 가지 조합의 타일을 각 $2$ 개씩 총 $32$ 개를 나눠가진 뒤 잘 섞은 이후 주머니에 넣습니다. 그 이후 주머니에서 타일을 $5$ 개 뽑아서 모두가 볼 수 있도록 자기 앞에 놓습니다. ¹

배치 단계

배치 단계는 선공부터 번갈아가면서 각 사람이 $32$ 번씩 총 $64$ 번 진행합니다.

자기 앞에 놓인 타일 중 하나를 게임보드의 칸 중 하나에 배치합니다.
주머니에 남은 타일이 있을 경우, 주머니에서 타일을 하나 뽑아와서 자기 앞에 놓습니다. ¹ 마지막 다섯 번의 배치 단계에서는 주머니에 타일이 존재하지 않고, 이 경우 주머니에서 타일을 가져오는 과정은 생략합니다.

점수 계산

인접한 두 칸에 놓인 타일이 같은 색이면 두 타일은 색으로 연결, 같은 문양이면 문양으로 연결되어 있습니다.

다음 두 가지 방법 중 편한 방법을 택해서 점수 계산을 진행합니다. 두 방법으로 계산된 점수는 같습니다. 두 사람 중 점수가 높은 사람이 승리하며, 점수가 같으면 무승부입니다.

타일별 계산

선공과 후공은 각자 다른 방법으로 타일의 점수를 계산합니다. 각 타일의 점수는

선공: 같은 문양으로 간접 연결²된 타일의 개수
후공: 같은 색으로 간접 연결²된 타일의 개수

입니다. 각 사람의 점수는 모든 타일 점수의 합입니다.

그룹별 계산

선공과 후공은 각자 다른 방법으로 타일들을 그룹으로 나눕니다.

선공: 같은 문양으로 연결을 따라 도달할 수 있는 타일 전체를 한 그룹으로 묶습니다.
후공: 같은 색으로 연결을 따라 도달할 수 있는 타일 전체를 한 그룹으로 묶습니다.

각 그룹의 점수는 $(\text{그룹에 속한 타일 개수})^2$ 입니다. 모든 그룹의 점수 합이 자신의 점수입니다.

점수 계산 예시

위 그림은 (a4+, G2); (a5-, G1); (b4-, B2); (b4+, Y2); (b5-, Y4); (b5+, R4); (b6-, B4); (c4+, R3); (c5-, R2); (c5+, Y2) 위치에 타일이 놓여있는 상태입니다. 이 상태의 점수계산은 다음과 같습니다.

선공

1 (): $1\textrm{점} \times 1\textrm{개} = 1\textrm{점}$
2 (): $3\textrm{점} \times 3\textrm{개} + 2\textrm{점} \times 2\textrm{개} = 13\textrm{점}$
3 (): $1\textrm{점} \times 1\textrm{개} = 1\textrm{점}$
4 (): $3\textrm{점} \times 3\textrm{개} = 9\textrm{점}$

총점: $1\textrm{점}+13\textrm{점}+1\textrm{점}+9\textrm{점} = 24\textrm{점}$

후공

R (): $3\textrm{점} \times 3\textrm{개} = 9\textrm{점}$
Y (): $2\textrm{점} \times 2\textrm{개} + 1\textrm{점} \times 1\textrm{개} = 5\textrm{점}$
G (): $2\textrm{점} \times 2\textrm{개} = 4\textrm{점}$
B (): $1\textrm{점} \times 1\textrm{개} + 1\textrm{점} \times 1\textrm{개} = 2\textrm{점}$

총점: $9\textrm{점}+5\textrm{점}+4\textrm{점}+2\textrm{점} = 20\textrm{점}$

입/출력 형식

참가자의 프로그램은 한 줄씩 입력을 받아 각 명령에 따라 동작해야 합니다. 출력이 필요한 명령은 아래 표에서 빨간색으로 시간 제한과 함께 표시되어 있습니다. 이 시간 제한 안에 출력을 하지 못한 경우 시간 초과 (TLE) 판정을 받게 되며, 해당 게임에서 실격패 처리됩니다.

커맨드	입력 형식	설명
READY	`READY (FIRST\|SECOND)`	플레이어의 선공/후공 정보를 알려주는 명령입니다. `FIRST`가 선공이며, `SECOND`가 후공입니다. 입력 준비 완료를 의미하는 `OK`를 $\textbf{3\,000}$ ms 이내에 출력해야 합니다.
INIT	`INIT A₁ A₂ A₃ A₄ A₅ B₁ B₂ B₃ B₄ B₅`	준비 단계에서 본인이 뽑은 타일이 $A_1, A_2, A_3, A_4, A_5$ 이고 상대가 뽑은 타일이 $B_1, B_2, B_3, B_4, B_5$ 임을 나타냅니다.
TIME	`TIME t₁ t₂`	자신의 배치 단계에 시작에서 현재까지 각 플레이어의 남은 시간을 알려주는 명령입니다. $t_1$ 은 내 프로그램의 남은 시간이고, $t_2$ 는 상대 프로그램의 남은 시간입니다. 단위는 ms입니다. 이후 $t_1$ ms 이내에 $p$ 위치에 $T$ 타일을 배치한다는 의미의 `PUT p T`를 출력해야합니다. 처음 $t_1$ , $t_2$ 로 주어지는 시간은 `READY` 명령어에 사용한 시간과 관련 없이 $10\,000$ ms입니다.
GET	`GET T`	$T$ 타일을 뽑아온 이후 자신의 배치 단계를 종료했음을 의미합니다. 주머니에 타일이 없어서 타일을 뽑아오지 않은 경우 $T$ 는 `X0`으로 주어집니다. 출력은 필요하지 않습니다.
OPP	`OPP p T₁ T₂ t`	상대의 배치 단계에서 $p$ 위치에 $T_1$ 타일을 배치하고 $T_2$ 타일을 뽑아왔음을 의미합니다. 주머니에 타일이 없어서 타일을 뽑아오지 않은 경우 $T_2$ 는 `X0`으로 주어집니다. 출력은 필요하지 않습니다.
FINISH	`FINISH`	게임 종료를 알리는 명령입니다. 이 명령을 받으면 게임 진행 상황에 관계 없이 프로그램은 즉시 정상적으로 종료되어야 하며, 출력은 필요하지 않습니다.

모든 명령어는 한 줄에 하나씩 입출력해야 하며, 출력할 때는 개행문자를 출력한 뒤 버퍼를 flush해야 합니다. 언어별로 버퍼를 flush하는 방법에 대해서는 각 언어의 공식 레퍼런스 문서와 예제 코드를 참고해 주세요.

예제 코드

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

C20: sample-code.c
C++20: sample-code.cpp
C#: sample-code.cs
OpenJDK Java 21: sample-code.java
Node.js: sample-code.rs
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

예제코드는 현재 배치 가능한 위치와 타일 중, 자신이 얻을 수 있는 점수가 가장 높은 곳에 배치합니다.

샘플 AI와의 대결

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

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

테스팅 툴 (GUI)

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

64비트 Windows (x86-64) (다운로드)
- 다운로드받은 .exe 파일을 실행합니다.
MacOS Universal (다운로드)
- .dmg 파일을 더블 클릭한 이후 testing-tool-connexion 파일을 Applications 폴더에 드래그해서 복사합니다. 그 이후 testing-tool-connexion 앱을 실행합니다.
- 사용자의 보안 설정은 App Store에서 다운로드한 응용 프로그램의 설치만 허용합니다. 라는 안내가 나오는 경우, "설정 > 개인정보 및 보안"에서 앱의 정보를 확인합니다.
deb (Ubuntu/Debian AMD64) (다운로드)
- apt 혹은 dpkg을 이용해 .deb 파일을 설치한 이후 testing-tool-connexion을 실행합니다.
rpm (Fedora/RHEL x86-64) (다운로드)
- rpm 혹은 yum을 이용해 .rpm 파일을 설치한 이후 testing-tool-connexion을 실행합니다.

테스팅 툴 (CLI)

참가자가 작성한 프로그램을 테스팅하기 위한 테스팅 툴 패키지인 testing-tool-connexion.zip (다운로드) 가 주어집니다. 자세한 내용은 파일 안에 있는 README.md를 참고하세요.

CLI 테스팅 툴을 수정하는 것은 자유이며, 실행 방법과 관련해서는 다른 사람과 자유롭게 토론할 수 있습니다. 하지만 수정된 테스팅 툴 혹은 테스팅 툴이 출력한 로그 파일 등을 팀원 이외의 사람과 공유하거나, 이와 관해 토론해서는 안됩니다.

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

시각화 도구

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

예시

예시 입력

R1 Y3 B1 G4 Y1 B3 Y2 R3 G1 R2 G3 G1 R2 R1 B4 G4 B2 Y2 R3 Y4 B1 R4 B4 B2 Y4 G2 R4 Y3 G2 B3 G3 Y1
G3 Y3 R1 Y2 R3 R1 Y1 B1 G1 R3 G2 Y4 Y2 Y3 B3 B2 B4 G2 R2 B4 R4 Y1 G4 R4 G3 Y4 G1 G4 B1 R2 B2 B3

예시 인터랙션

선공 입력	선공 출력	후공 입력	후공 출력	로그
`READY FIRST`	`OK`	`READY SECOND`	`OK`
`INIT R1 Y3 B1 G4 Y1 G3 Y3 R1 Y2 R3`		`INIT G3 Y3 R1 Y2 R3 R1 Y3 B1 G4 Y1`		`INIT R1 Y3 B1 G4 Y1 G3 Y3 R1 Y2 R3`
`TIME 10000 10000`	(70ms 소요) `PUT a1+ R1`
`GET B3`		`OPP a1+ R1 B3 70`		`FIRST a1+ R1 B3 70`
		`TIME 10000 9930`	(40ms 소요) `PUT a2- R1`
`OPP a2- R1 R1 40`		`GET R1`		`SECOND a2- R1 R1 40`
`TIME 9930 9960`	(80ms 소요) `PUT a2+ B1`
`GET Y2`		`OPP a2+ B1 Y2 80`		`FIRST a2+ B1 Y2 80`
		`TIME 9960 9850`	(50ms 소요) `PUT b1- R3`
`OPP b1- R3 Y1 50`		`GET Y1`		`SECOND b1- R3 Y1 50`
		(중략)
		`TIME 980 1730`	(100ms 소요) `PUT f4+ Y1`
`OPP f4+ Y1 X0 100`		`GET X0`		`SECOND f4+ Y1 X0 100`
`FINISH`	(프로그램 종료)	`FINISH`	(프로그램 종료)	`FINISH`
				`SCOREFIRST 314` `SCORESECOND 270`