[BOJ] 12110.2048(Easy)

 

12100번: 2048 (Easy)

N*N 크기의 보드에서 2048 게임과 유사하게 게임이 진행됩니다.

2048의 경우 이동 시 새로운 블록이 추가되지만, 해당 문제에서는 처음 주어진 블록으로만 진행합니다.

상하좌우로 이동이 가능하며 총 5번의 이동 후 가장 큰 블록의 값을 출력하는 문제입니다.

이 때, 이동을 하며 같은 수의 블록은 합쳐집니다. 그러나 한 번 합쳐진 블록은 다시 합칠 수 없습니다.

즉, 4 4 8 8 이라는 블록이 주어지면 결과가 8 16 이 된다는 의미입니다.

 

블록의 값은 모두 스택으로 관리하며, check 변수를 이용해 블록의 합쳐짐 여부를 관리했습니다.

모든 수는 스택에 저장하여 관리합니다. 그러나 현재 블록이 이전의 블록과 같은 값을 가지면 합쳐줍니다.

스택에서 이전 값을 꺼내고 현재 블록과 더해준 후 스택에 추가하는 방식으로 진행했습니다.

이 때, check 변수를 1로 만들어 주어 다음 블록의 값이 같은 값이더라도 더할 수 없게 했습니다.

 

코드는 다음과 같습니다.

import sys

def up(board) : # 위로 이동
    for c in range(N) : # N번 반복을 통해 모든 열에 대해 수행
        stack = []
        check = 0
        for r in range(N) :
            if board[r][c] > 0 :
                if len(stack) > 0 and stack[-1] == board[r][c] and check == 0 :
                    stack.append(stack.pop() + board[r][c])
                    check = 1
                else :
                    stack.append(board[r][c])
                    check = 0
        for r in range(N) :
            if 0 <= r < len(stack) : board[r][c] = stack[r]
            else : board[r][c] = 0
    return board
        

def down(board) : # 아래로 이동
    for c in range(N) : # N번 반복을 통해 모든 열에 대해 수행
        stack = []
        check = 0
        for r in range(N - 1, -1, -1) :
            if board[r][c] > 0 :
                if len(stack) > 0 and stack[-1] == board[r][c] and check == 0 :
                    stack.append(stack.pop() + board[r][c])
                    check = 1
                else :
                    stack.append(board[r][c])
                    check = 0
        for r in range(N) :
            if 0 <= (N - r - 1) < len(stack) : board[r][c] = stack[N - r - 1]
            else : board[r][c] = 0
    return board

def left(board) : # 왼쪽으로 이동
    for r in range(N) : # N번 반복을 통해 모든 열에 대해 수행
        stack = []
        check = 0
        for c in range(N) :
            if board[r][c] > 0 :
                if len(stack) > 0 and stack[-1] == board[r][c] and check == 0 :
                    stack.append(stack.pop() + board[r][c])
                    check = 1
                else :
                    stack.append(board[r][c])
                    check = 0
        for c in range(N) :
            if 0 <= c < len(stack) : board[r][c] = stack[c]
            else : board[r][c] = 0
    return board

def right(board) : # 오른쪽으로 이동
    for r in range(N) : # N번 반복을 통해 모든 열에 대해 수행
        stack = []
        check = 0
        for c in range(N - 1, -1, -1) :
            if board[r][c] > 0 :
                if len(stack) > 0 and stack[-1] == board[r][c] and check == 0 :
                    stack.append(stack.pop() + board[r][c])
                    check = 1
                else :
                    stack.append(board[r][c])
                    check = 0
        for c in range(N) :
            if 0 <= (N - c - 1) < len(stack) : board[r][c] = stack[N - c - 1]
            else : board[r][c] = 0
    return board

def find_max(board) :
    global max_
    for b in board :
        temp = max(b)
        max_ = max(max_, temp)

def dfs(copy_board, L) :
    global max_
    if L == 5 :
        find_max(copy_board)
        return
    dfs(up([copy[:] for copy in copy_board]), L + 1)
    dfs(down([copy[:] for copy in copy_board]), L + 1)
    dfs(left([copy[:] for copy in copy_board]), L + 1)
    dfs(right([copy[:] for copy in copy_board]), L + 1)

if __name__=="__main__" :
    input = sys.stdin.readline

    N = int(input()) # 보드 크기
    board = [list(map(int, input().split())) for _ in range(N)]
    max_ = 0
    dfs(board, 0)
    print(max_)