[Python] 백준 12100번: 2048 (Easy)

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

12100번: 2048 (Easy)

import sys
import copy

input = sys.stdin.readline

TOP, RIGHT, BOTTOM, LEFT = 0, 1, 2, 3
dx = [-1, 0, 1, 0]
dy = [0, 1, 0, -1]


def dfs(count):
    global board

    if count == 5:
        setMaxBlock(board)
        return

    for i in range(4):
        prevBoard = copy.deepcopy(board)
        setBoard(i)
        dfs(count+1)
        board = prevBoard


def setBoard(direction):
    global board
    reversedDirection = (direction+2) % 4

    for index in range(N):
        if direction == TOP:
            startX, startY = 0, index
        elif direction == RIGHT:
            startX, startY = index, N-1
        elif direction == BOTTOM:
            startX, startY = N-1, index
        elif direction == LEFT:
            startX, startY = index, 0

        # push numbers in queue
        curX, curY = startX, startY
        queue = []
        while 0 <= curX <= N-1 and 0 <= curY <= N-1:
            curNumber = board[curX][curY]
            if curNumber != 0:
                queue.append(curNumber)

            curX += dx[reversedDirection]
            curY += dy[reversedDirection]

        # merge
        i = 0
        while i < len(queue)-1:
            if queue[i] == queue[i+1]:
                queue[i] *= 2
                del queue[i+1]
            i += 1

        # align
        curX, curY = startX, startY
        while 0 <= curX <= N-1 and 0 <= curY <= N-1:
            if len(queue) >= 1:
                board[curX][curY] = queue.pop(0)
            else:
                board[curX][curY] = 0

            curX += dx[reversedDirection]
            curY += dy[reversedDirection]


def setMaxBlock(board):
    global maxBlock

    for i in range(N):
        for j in range(N):
            maxBlock = max(maxBlock, board[i][j])


N = int(input())
board = [list(map(int, input().split())) for _ in range(N)]


maxBlock = 0
dfs(0)
print(maxBlock)

 

큰 틀은, setBoard() 함수를 통해 보드를 변형시키면서 dfs + backtracking을 돌려주고, count가 5일 때 해당 보드에서의 최댓값을 구해주는 형태이다.

 

setBoard()가 핵심이며, 이동방향에 따라 curX, curY가 적절히 이동하도록 설정하였다. 우선, 현재 라인([2,0,8,0,2,2,2]라고 하자.)에서 0이 아닌 숫자만을 차례대로 담아준다. 다음으로 큐([2,8,2,2,2])를 돌면서, 인접한 숫자가 같을 경우 이 숫자들을 병합해준다. 끝으로 board에 큐([2,8,4,2])의 값들을 순서대로 할당하고, 큐가 끝났을 경우 나머지는 모두 0을 삽입해준다.

여기서 중요한 건 curX, curY의 시작점과 이동방향이다. direction이 LEFT이고 for문을 통해 돌고 있는 현재의 라인이, 위의 예시처럼, [2,0,8,0,2,2,2]라고 하자. 이 때 curX, curY는 index, 0부터 시작해서 index, N-1까지 '오른쪽'으로 이동하기 때문에, 스택은 push 단계에서 [2,8,2,2,2]가 되고 merge 단계에서 [2,8,4,2]가 되는 것이다. 만약 N-1~0, 즉 왼쪽으로 돌았다면 원하는 스택을 얻지 못했을 것이다.