메이플 월드의 평화로운 숲속, 예티와 핑크빈은 오늘도 사이좋게 버섯 밭을 가꾸고 있었습니다.
그러던 어느 날, 버섯마다 숫자가 적혀 있다는 사실을 발견한 두 친구는 이 숫자를 활용해 새로운 게임을 만들기로 했습니다.
그들은 버섯 밭의 일부를 점령하며 경쟁하는 게임을 고안했고, 아래의 규칙에 따라 번갈아 가며 영역을 선택해 나갑니다.
Rule 1
플레이어는 자신의 턴에 버섯 밭에서 하나의 직사각형 영역을 선택합니다.
Rule 2
선택한 영역 내의 숫자 합이 정확히 1010인 경우, 해당 영역의 버섯은 제거되며 플레이어가 그 영역을 점령합니다.
이때, 영역 안에 상대방이 이미 점령한 칸이 포함되어 있다면 해당 칸의 소유권도 빼앗을 수 있습니다.
또한, 선택한 직사각형의 네 변에는 각각 최소 하나 이상의 버섯이 영역 안쪽으로 인접해 있어야 합니다.
Rule 3
선택 가능한 영역이 없거나 전략적으로 선택을 하지 않으려 한다면, 선택을 생략하고 턴을 넘길 수 있습니다.
Rule 4
두 플레이어가 연속으로 턴을 넘기면 게임이 종료됩니다.
종료 시점에 더 많은 칸을 점령한 플레이어가 승리합니다.
온라인에서 최근에 유행한 사과게임을 모티브로 만든 게임이다. 안에 쓰여있는 수의 합이 10이 되는 직사각형을 선택, 그 땅을 점령하는 방식이다. 최종적으로 더 많은 땅을 가지고 있는 사람이 이긴다. 서버에 제출을 통해 샘플 Ai 14개와의 대결 결과를 살펴볼 수 있고, 매일 한 번의 vs 전국의 참여자 대결을 진행하여, 유저들과의 대결 결과를 살펴볼 수 있다. 연습게임 기간에는 팀들이 바빴기에, 거의 나 혼자 참가하였다.
우선 게임판의 크기가 $10 \times17$으로 매우 작으므로, 모든 직사각형을 살펴볼 수 있다. 모든 직사각형을 살펴보는 경우의 수는 행에서 2개의 변, 변에서 2개의 변을 고르는 경우의 수와 같으므로, $_{10}C_2 \times _{17}C_2 = 6120$가지이다. 또한 각 직사각형의 내부의 합을 구해야하므로, 각 직사각형 크기정도의 연산이 추가로 소요된다. 따라서 $n\times m$크기 게임판의 모든 직사각형을 살펴보는 시간복잡도는 대략 $O(n^2m^2)$의 연산이 필요하다. $10^217^2$의 값은 $28900$으로 보통 컴퓨터의 1초 연산량을 1억이라 하면 매우 작은 값이므로, 고려할 수 있는 전략이다. 또한 여기서 각 직사각형 내부의 합을 구하는 연산은 2차원 누적합을 통해서 $O(nm)$에 전처리 후 각 쿼리를 $O(1)$에 처리할 수 있으므로, 실질적인 시간복잡도는 $O(nm)$이다. 나는 가장 처음 접근으로, 모든 직사각형을 살펴보며 그리디한 전략을 써서 매 게임판 상태에서 얻을 수 있는 가장 큰 점수를 먹는 전략을 써 보았다.
결과는 샘플 Ai기준 4승 10패. 그렇게 좋은 결과는 아니였다.
코드:
# ================================
# Game 클래스: 게임 상태 관리
# ================================
class Game:
def __init__(self, board, first):
self.board = board # 게임 보드 (2차원 배열)
self.first = first # 선공 여부
self.passed = False # 마지막 턴에 패스했는지 여부
self.board_point = []
self.n = 10
self.m = 17
for i in range(self.n):
for j in range(self.m):
self.board_point.append((i,j))
# 사각형 (r1, c1) ~ (r2, c2)이 유효한지 검사 (합이 10이고, 네 변을 모두 포함)
def isValid(self, r1, c1, r2, c2):
sums = 0
r1fit = c1fit = r2fit = c2fit = False
for r in range(r1, r2 + 1):
for c in range(c1, c2 + 1):
if self.board[r][c] != 0:
sums += self.board[r][c]
if r == r1:
r1fit = True
if r == r2:
r2fit = True
if c == c1:
c1fit = True
if c == c2:
c2fit = True
return sums == 10 and r1fit and r2fit and c1fit and c2fit
def calc_psum(self):
psum = [[0]*(self.m+1) for _ in range(self.n+1)]
for i in range(1, self.n+1):
for j in range(1, self.m+1):
psum[i][j] = self.board[i-1][j-1]
for i in range(1, self.n):
for j in range(self.m):
psum[i][j+1] += psum[i][j]
for i in range(self.n):
for j in range(1, self.m):
psum[i+1][j] += psum[i][j]
return psum
def psum_val(self, r1, c1, r2, c2, psum):
return psum[r2+1][c2+1] - psum[r1][c2+1] - psum[r2+1][c2] + psum[r1][c1]
# ================================================================
# ===================== [필수 구현] ===============================
# 합이 10인 유효한 사각형을 찾아 (r1, c1, r2, c2) 튜플로 반환
# 없으면 (-1, -1, -1, -1) 반환 (패스 의미)
# ================================================================
def calculateMove(self, _myTime, _oppTime):
psum = self.calc_psum()
is_find = 0
ret = [-1,-1,-1,-1]
rect_size = 0
for i in range(len(self.board_point)):
for j in range(i+1, len(self.board_point)):
p1 = self.board_point[i]
p2 = self.board_point[j]
if self.psum_val(*p1, *p2, psum) == 10:
if self.isValid(*p1, *p2):
if is_find:
rect = (p2[0] - p1[0] + 1) * (p2[1] - p1[1] + 1)
if rect_size < rect:
rect_size = rect
ret = list(p1 + p2)
else:
is_find = 1
ret = list(p1 + p2)
return tuple(ret)
# =================== [필수 구현 끝] =============================
# 상대방의 수를 받아 보드에 반영
def updateOpponentAction(self, action, _time):
self.updateMove(*action, False)
# 주어진 수를 보드에 반영 (칸을 0으로 지움)
def updateMove(self, r1, c1, r2, c2, _isMyMove):
if r1 == c1 == r2 == c2 == -1:
self.passed = True
return
for r in range(r1, r2 + 1):
for c in range(c1, c2 + 1):
self.board[r][c] = 0
self.passed = False
# ================================
# main(): 입출력 처리 및 게임 진행
# ================================
def main():
while True:
line = input().split()
if len(line) == 0:
continue
command, *param = line
if command == "READY":
# 선공 여부 확인
turn = param[0]
global first
first = turn == "FIRST"
print("OK", flush=True)
continue
if command == "INIT":
# 보드 초기화
board = [list(map(int, row)) for row in param]
global game
game = Game(board, first)
continue
if command == "TIME":
# 내 턴: 수 계산 및 실행
myTime, oppTime = map(int, param)
ret = game.calculateMove(myTime, oppTime)
game.updateMove(*ret, True)
print(*ret, flush=True)
continue
if command == "OPP":
# 상대 턴 반영
r1, c1, r2, c2, time = map(int, param)
game.updateOpponentAction((r1, c1, r2, c2), time)
continue
if command == "FINISH":
break
assert False, f"Invalid command {command}"
if __name__ == "__main__":
main()