[백준/파이썬] 12100번 2048

https://www.acmicpc.net/problem/12100

12100번: 2048 (Easy)

2048게임을 구현하는 문제이다. 실제 2048과 다른 점은, 움직일 때 새로운 블럭이 생성되지 않는다는 점이고 이동횟수가 5번으로 제한되어있다는 것이다.

전체적인 구성은 기본적인 dfs방식을 이용한 백트래킹+브루트포스와 동일하다.

 

다만 상,하,좌,우 이동 시 블럭들을 처리하는 것이 조금 까다롭다.

키포인트는 다음과 같다.

1. 합쳐지는 방향대로 각 열 또는 행들을 배열에 담는다. 이 때 값이 0인 블럭들은 넣지 않아야 한다! ( 2 0 2 를 왼쪽으로 밀면 4 0 0이 되어야하기 때문!)

2. 배열을 돌면서 자신의 바로 뒤 값과 같다면 2를 곱해주고 바로 뒤 값은 0으로 바꿔준다.

3. 합쳐진 배열(= 이동 결과 값)을 다시 보드에 채워준다.

 

또한 매 move마다 board를 넘겨주는데, count가 5가 되어서 return 되었을 때 다시 직전의 보드 상태로 돌아와야 하므로 deepcopy를 이용해 보드롤 복사하여 전달하고, move 결과를 전달받으면 된다!

from copy import deepcopy
import sys
sys.setrecursionlimit(10**6)
input = sys.stdin.readline

n = int(input())
board = [list(map(int, input().split())) for _ in range(n)]
ans = -1

def move(map,dx):
  arr=[]
  if dx == 0: # up
    for j in range(n):
      for i in range(n):
        if map[i][j]:
          arr.append(map[i][j])
          map[i][j] = 0
          
      for k in range(len(arr)-1):
        if arr[k]==arr[k+1]:
          arr[k] = arr[k]*2
          arr[k+1] = 0

      idx = 0
      for x in arr:
        if x != 0:
          map[idx][j] = x
          idx+=1
      arr=[]
          
  elif dx == 1: # down
    for j in range(n):
      for i in range(n-1,-1,-1):
        if map[i][j]:
          arr.append(map[i][j])
          map[i][j] = 0
          
      for k in range(len(arr)-1):
        if arr[k]==arr[k+1]:
          arr[k] = arr[k]*2
          arr[k+1] = 0
          
      idx = n-1
      for x in arr:
        if x != 0:
          map[idx][j] = x
          idx-=1
      arr=[]
          
  elif dx == 2: # left
    for i in range(n):
      for j in range(n):
        if map[i][j]:
          arr.append(map[i][j])
          map[i][j] = 0
          
      for k in range(len(arr)-1):
        if arr[k]==arr[k+1]:
          arr[k] = arr[k]*2
          arr[k+1] = 0
          
      idx = 0
      for x in arr:
        if x != 0:
          map[i][idx] = x
          idx+=1
      arr=[]
          
  elif dx == 3: # right
    for i in range(n):
      for j in range(n-1,-1,-1):
        if map[i][j]:
          arr.append(map[i][j])
          map[i][j] = 0
          
      for k in range(len(arr)-1):
        if arr[k]==arr[k+1]:
          arr[k] = arr[k]*2
          arr[k+1] = 0
          
      idx = n-1
      for x in arr:
        if x != 0:
          map[i][idx] = x
          idx-=1
      arr=[]
      
  return map

def dfs(board, count):
    global ans
    if count == 5:
      for i in range(n):
        ans = max(ans, max(board[i]))
      return
    
    for k in range(4):
      tmp_board = move(deepcopy(board),k) 
      dfs(tmp_board,count+1)
dfs(board,0)
print(ans)