[BOJ] 2048 (Easy) (12100, G1)

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

빡구현 문제인데, 골드 1 치고는 정말 쉽다.
기본적으로 5번의 명령을 받는 것은 DFS긴 하다.  5번 정도니까, 크게 뭐 할 거 없이 모두 다 시도해보면 된다.

문제는 2048을 어떻게 구현할 것이냐인데, 줄별로 뽑아서 만들면 된다.

스와이프 하면, 그 방향으로 중력이 적용되어 모든 공백이 없어지고 같은 숫자는 딱 한 번만 더해진다.
추가로, 우선순위는 그 방향의 최초 두개 부터다 (예시 - 8 8 8 0 에서 좌측 스와이프는 8 16 0 0 이 아니라 16 8 0 0)

이를 구현할 방법은 다음과 같다.

1. 모든 0을 다 반대쪽으로 옮겨 준다.
2. 맨 앞부터 두개씩 비교하여 같은 숫자면 더 스와이프 방향에 가까운 쪽에 수를 몰아주고, 반대쪽은 0으로 만든다.
3. 이를 줄 끝 까지 확인한다.

이를 계속 반복한다. 5층까지라서 4^5 = 1024 경우면 충분하다. 어렵지 않다.

import sys
import copy
input = sys.stdin.readline
move_keyword = ['L', 'R', 'U', 'D']
# 0을 우측으로 옮기는 상황
def zero_move(a):
    length = len(a)
    result = []
    for cur_a in a:
        if cur_a != 0:
            result.append(cur_a)
    while len(result) < length:
        result.append(0)
    return result
    
def move_left(board):
    for i in range(N):
        # step 1 / 0을 몰아준다.
        cur_row = board[i]
        cur_row = zero_move(cur_row)
        # step 2 / 좌우가 같으면 좌측에 2배, 우측에 0을 준다.
        for j in range(1, N):
            if cur_row[j-1] == cur_row[j]:
                cur_row[j-1] *= 2
                cur_row[j] = 0
        cur_row = zero_move(cur_row)
        for j in range(N):
            board[i][j] = cur_row[j]
    return board

def move_right(board):
    for i in range(N):
        cur_row = board[i][::-1]
        # step 1 / 뒤집어서 0을 몰아주면 된다.
        cur_row = zero_move(cur_row)
        # step 2 / 좌우가 같으면 좌측에 2배, 우측에 0을 준다.
        for j in range(1, N):
            if cur_row[j-1] == cur_row[j]:
                cur_row[j-1] *= 2
                cur_row[j] = 0
        cur_row = zero_move(cur_row)[::-1]
        for j in range(N):
            board[i][j] = cur_row[j]
    return board

def move_up(board):
    for i in range(N):
        cur_row = []
        for j in range(N):
            cur_row.append(board[j][i])
        cur_row = zero_move(cur_row)
        # step 2 / 좌우가 같으면 좌측에 2배, 우측에 0을 준다.
        for j in range(1, N):
            if cur_row[j-1] == cur_row[j]:
                cur_row[j-1] *= 2
                cur_row[j] = 0
        cur_row = zero_move(cur_row)
        for j in range(N):
            board[j][i] = cur_row[j]
    return board
        
def move_down(board):
    for i in range(N):
        cur_row = []
        for j in range(N):
            cur_row.append(board[j][i])
        cur_row = cur_row[::-1]
        cur_row = zero_move(cur_row)
        # step 2 / 좌우가 같으면 좌측에 2배, 우측에 0을 준다.
        for j in range(1, N):
            if cur_row[j-1] == cur_row[j]:
                cur_row[j-1] *= 2
                cur_row[j] = 0
        cur_row = zero_move(cur_row)[::-1]
        for j in range(N):
            board[j][i] = cur_row[j]
    return board

def dfs(level, key_list):
    global answer
    if level == 5:
        cur_try = copy.deepcopy(board)
        for k in key_list:
            if k == 'L':
                cur_try = move_left(cur_try)
            elif k == 'R':
                cur_try = move_right(cur_try)
            elif k == 'U':
                cur_try = move_up(cur_try)
            elif k == 'D':
                cur_try = move_down(cur_try)
        max_val = 0
        for i in range(N):
            for j in range(N):
                max_val = max(max_val, cur_try[i][j])
        answer = max(max_val, answer)
        return
    else:
        for m in move_keyword:
            key_list.append(m)
            dfs(level + 1, key_list)
            key_list.pop()

N = int(input())
board = []
for _ in range(N):
    board.append(list(map(int, input().split())))
answer = 0
dfs(0, [])
print(answer)