[Gold II]
https://www.acmicpc.net/problem/12100
12100번: 2048 (Easy)
첫째 줄에 보드의 크기 N (1 ≤ N ≤ 20)이 주어진다. 둘째 줄부터 N개의 줄에는 게임판의 초기 상태가 주어진다. 0은 빈 칸을 나타내며, 이외의 값은 모두 블록을 나타낸다. 블록에 쓰여 있는 수는 2
www.acmicpc.net
풀이
유명한 2048 게임을 구현하는 문제였다..
일단 보드의 크기도 최대 1<=N<=20으로, 400칸이 최대이고,
5번까지만 이동시키기 때문에, 4^5 = 2^10 = 1024의 경우의 수밖에 나오지 않는다.
따라서, 모든 경우의 수를 검사한다고 하더라도, TLE(시간초과)가 나지 않을 것이라는 믿음을 가지고 Brute-Force로 구현했다.
left 함수 하나만 구현해놓고 행렬을 돌려서 풀어볼까 싶었는데, 그냥 left right up down 다 구현했다.
구현하는 것 자체는 어렵지 않았으나, python은 함수 parameter로 넘겨줄때 deep-copy가 되지 않아서.. 그것 때문에 애를 먹었던 문제.
list slicing으로 deep copy를 하려 했는데, 2차원 list라서 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))