(골드Ⅱ)
https://www.acmicpc.net/problem/12100
제12100:2048호(단순)
첫 번째 줄은 체커보드 크기 N(1 ≤ N ≤ 20)을 제공합니다. 게임 보드의 초기 상태는 두 번째 줄부터 시작하여 N 줄에 주어집니다. 0은 빈 셀을 나타내고 다른 모든 값은 블록을 나타냅니다. 블록에 적힌 숫자는 2입니다.
www.acmicpc.net
설명하다
유명한 2048 게임을 구현하는 문제입니다.
먼저 체스판의 최대 크기는 1<=N<=20이며 최대 400칸,
최대 5개의 이동만 있기 때문에 4^5 = 2^10 = 1024개의 경우만 있습니다.
따라서 모든 경우를 확인하더라도 TLE(시간 초과)가 발생하지 않을 것이라고 믿고 무차별 대입 방식으로 구현됩니다.
이를 해결하기 위해 하나의 left 함수만 구현하고 이를 행렬로 변환하여 해결하고 싶었고, 결과적으로 left right up down을 직접 구현했습니다.
구현하기 어렵지는 않지만 Python이 함수 인수로 전달할 때 깊은 복사가 수행되지 않습니다.
리스트 슬라이싱으로 딥카피 하려고 하는데 2D 리스트라서 copy.deepcopy() 결국 써봐야 알 것 같아요. 다행히도 사용하더라도 TLE가 발생하지 않습니다.
차근차근 해보면 난이도 면에서 어렵지 않다.
import sys
import copy
sys.setrecursionlimit(2**11)
N = int(input())
Board = (list(map(int, input().split())) for _ in range(N))
result_max = ()
def left(board):
for row in board:
# 왼쪽으로 당기기
tempIndex = 0
for index in range(N):
if row(index) != 0:
# 0과 오른쪽의 숫자를 swap하여 왼쪽으로 당김
row(index), row(tempIndex) = row(tempIndex), row(index)
tempIndex += 1
# 왼쪽으로 밀면서 같은 숫자 합치기
temp = 0
index = 0
while index < N:
if row(index) == 0:
# 왼쪽으로 이미 밀었으므로, 0을 만나면 종료
break
else:
# 앞의 숫자와 같다면
if temp == row(index):
row(index-1) *= 2
# 앞의 숫자를 2배로 하고, 뒤의 숫자들을 하나씩 당김
j = index
while j < N-1:
row(j) = row(j+1)
j += 1
row(-1) = 0
temp = 0
# 합쳐져서 한 칸 당겼다면 다시 그 index부터 검사
index -= 1
else:
temp = row(index)
index += 1
return board
def right(board):
for row in board:
# 오른쪽으로 당기기
tempIndex = N-1
for index in range(N-1, -1, -1):
if row(index) != 0:
# 0과 왼쪽의 숫자를 swap하여 오른쪽으로 당김
row(index), row(tempIndex) = row(tempIndex), row(index)
tempIndex -= 1
# 오른쪽으로 밀면서 같은 숫자 합치기
temp = 0
index = N-1
while index >= 0:
if row(index) == 0:
# 오른쪽으로 이미 밀었으므로, 0을 만나면 종료
break
else:
# 뒤의 숫자와 같다면
if temp == row(index):
row(index+1) *= 2
# 뒤의 숫자를 2배로 하고, 뒤의 숫자들을 하나씩 당김
j = index
while j > 0:
row(j) = row(j-1)
j -= 1
row(0) = 0
temp = 0
# 합쳐져서 한 칸 당겼다면 다시 그 index부터 검사
index += 1
else:
temp = row(index)
index -= 1
return board
def up(board):
for col in range(N):
# column = board(0 ~ N-1)(col)
# 위로 당기기
tempIndex = 0
for index in range(N):
if board(index)(col) != 0:
# 0과 아래의 숫자를 swap해 위로 당김
board(index)(col), board(tempIndex)(col) = board(tempIndex)(col), board(index)(col)
tempIndex += 1
# 위로 밀면서 같은 숫자 합치기
temp = 0
index = 0
while index < N:
if board(index)(col) == 0:
# 위로 이미 밀었으므로, 0을 만나면 종료
break
else:
# 위의 숫자와 같다면
if temp == board(index)(col):
# 위의 숫자를 2배로 하고, 아래부터 한칸씩 당김
board(index-1)(col) *= 2
j = index
while j < N-1:
board(j)(col) = board(j+1)(col)
j += 1
board(-1)(col) = 0
temp = 0
index -= 1
else:
temp = board(index)(col)
index += 1
return board
def down(board):
for col in range(N):
# column = board(0 ~ N-1)(col)
# 아래로 당기기
tempIndex = N-1
for index in range(N-1, -1, -1):
if board(index)(col) != 0:
# 0과 위의 숫자를 swap해 아래로 당김
board(index)(col), board(tempIndex)(col) = board(tempIndex)(col), board(index)(col)
tempIndex -= 1
# 아래로 밀면서 같은 숫자 합치기
temp = 0
index = N-1
while index >= 0:
if board(index)(col) == 0:
# 아래로 이미 밀었으므로, 0을 만나면 종료
break
else:
# 아래의 숫자와 같다면
if temp == board(index)(col):
# 아래의 숫자를 2배로 하고, 아래부터 한칸씩 당김
board(index+1)(col) *= 2
j = index
while j > 0:
board(j)(col) = board(j-1)(col)
j -= 1
board(0)(col) = 0
temp = 0
index += 1
else:
temp = board(index)(col)
index -= 1
return board
def dfs(board, depth: int):
if depth == 5:
result_max.append(max(map(max, board)))
return
# left
dfs(left(copy.deepcopy(board)), depth+1)
# right
dfs(right(copy.deepcopy(board)), depth+1)
# up
dfs(up(copy.deepcopy(board)), depth+1)
# down
dfs(down(copy.deepcopy(board)), depth+1)
dfs(copy.deepcopy(Board), 0)
print(max(result_max))