728x90
12100번: 2048 (Easy)
첫째 줄에 보드의 크기 N (1 ≤ N ≤ 20)이 주어진다. 둘째 줄부터 N개의 줄에는 게임판의 초기 상태가 주어진다. 0은 빈 칸을 나타내며, 이외의 값은 모두 블록을 나타낸다. 블록에 쓰여 있는 수는 2
www.acmicpc.net
분석
네 방향으로 dfs 를 통해 다섯번 밀면서 보드의 최댓값 갱신
풀이
"""
2048 게임은 보드의 크기가 N×N 이다. 보드의 크기와 보드판의 블록 상태가 주어졌을 때, 최대 5번 이동해서 만들 수 있는 가장 큰 블록의 값
블록이 추가되는 경우는 없다
이동하려고 하는 쪽의 칸이 먼저 합쳐진다. 예를 들어, 위로 이동시키는 경우에는 위쪽에 있는 블록이 먼저 합쳐지게 된다
최대 5번 이동시켜서 얻을 수 있는 가장 큰 블록을 출력한다.
3
2 2 2
4 4 4
8 8 8
"""
import sys, copy
input=sys.stdin.readline
sys.setrecursionlimit(10**9)
n=int(input())
board=[list(map(int,input().split())) for _ in range(n)]
res = 0
def move(dir):
if dir == 0: # 위로 밀기
for j in range(n):
idx = 0
for i in range(1, n):
if board[i][j]:
temp = board[i][j]
board[i][j] = 0
if board[idx][j] == 0: # 비어있으면
board[idx][j] = temp
elif board[idx][j] == temp: # 같으면
board[idx][j] = temp * 2 # 합체
idx += 1
else: # 다르면
idx += 1
board[idx][j] = temp
elif dir == 1: # 아래로 밀기
for j in range(n):
idx = n-1
for i in range(n - 2, -1, -1):
if board[i][j]:
temp = board[i][j]
board[i][j] = 0
if board[idx][j] == 0:
board[idx][j] = temp
elif board[idx][j] == temp:
board[idx][j] = temp * 2
idx -= 1
else:
idx -= 1
board[idx][j] = temp
elif dir == 2: # 왼쪽으로 밀기
for i in range(n):
idx = 0
for j in range(1, n):
if board[i][j]:
temp = board[i][j]
board[i][j] = 0
if board[i][idx] == 0:
board[i][idx] = temp
elif board[i][idx] == temp:
board[i][idx] = temp * 2
idx += 1
else:
idx += 1
board[i][idx] = temp
else: # 오른쪽으로 밀기
for i in range(n):
idx = n-1
for j in range(n - 2, -1, -1):
if board[i][j]:
temp = board[i][j]
board[i][j] = 0
if board[i][idx] == 0:
board[i][idx] = temp
elif board[i][idx] == temp:
board[i][idx] = temp * 2
idx -= 1
else:
idx -= 1
board[i][idx] = temp
def dfs(cnt):
global board, res
if cnt == 5:
# 보드 최댓값 찾기
for i in range(n):
for j in range(n):
res = max(res, board[i][j])
return
temp_a = copy.deepcopy(board)
for i in range(4): # 네방향으로 밀기
move(i)
dfs(cnt+1)
board = copy.deepcopy(temp_a) # 초기화
print(board, cnt)
print()
dfs(0)
print(res)728x90