[BOJ 12100] 2048(Easy), Python

4%에서 틀렸습니다를 맞고 코드를 수정하여 해결했다. 여기서 틀리면 숫자를 합칠때 이미 합쳐진 숫자는 다시 합쳐지지 않는다는 것을 잘못 구현했기 때문이다. (그림12 -> 그림13의 설명을 다시 읽어보자)

유틸리티 함수

print_board()

숫자블록들을 모두 출력하는 함수.

board_copy()

현재 숫자블록들을 복사하여 새로운 블록을 반환하는 함수.

isChange()

블록을 상하좌우로 이동시킨 후 변화가 있는지 확인하는 함수.

변화가 없다면 더 이상 탐색할 필요가 없다.

getMaxValue()

2차원 블록에서 가장 큰 값을 반환하는 함수.

블록을 이동하는 함수

sliding()

1차원 배열을 왼쪽으로 이동시키는 함수. 이 1차원 배열은 column이나 row가 된다.

slide_up/left/down/right

2차원 배열을 상/좌/하/우로 이동하는 함수. sliding()을 기반으로 작성.

dfs()

2차원 배열을 DFS 탐색으로 블록을 이동시키고, 각 상태에서 블록의 최댓값을 갱신한다.

#import sys
#sys.stdin = open('input.txt', 'r')
#input = sys.stdin.readline

def print_board(board, N):
    print('=' * 10)
    for i in range(N):
        for j in range(N):
            print(board[i][j], end=' ')
        print()
    print('=' * 10, end='\n\n')

def sliding(L, N, isprint=False):
    if isprint: print(L)

    ismerged = [False] * N
    for i in range(1, N):
        while i > 0:
            if L[i - 1] == 0:
                L[i - 1] = L[i]
                L[i] = 0
            elif L[i - 1] == L[i] and not ismerged[i - 1] and not ismerged[i]:
                ismerged[i - 1] = True
                L[i - 1] *= 2
                L[i] = 0
            i -= 1
        if isprint: print(L, i)

    if isprint: print(L)


def slide_up(board, N):
    for col in range(N):
        tmp = []
        for i in range(N):
            tmp.append(board[i][col])
        sliding(tmp, N)
        for i in range(N):
            board[i][col] = tmp[i]

def slide_left(board, N):
    for row in range(N):
        tmp = []
        for i in range(N):
            tmp.append(board[row][i])
        sliding(tmp, N)
        for i in range(N):
            board[row][i] = tmp[i]

def slide_down(board, N):
    for col in range(N):
        tmp = []
        for i in range(N):
            tmp.append(board[i][col])
        tmp = tmp[::-1]
        sliding(tmp, N)
        tmp = tmp[::-1]
        for i in range(N):
            board[i][col] = tmp[i]

def slide_right(board, N):
    for row in range(N):
        tmp = []
        for i in range(N):
            tmp.append(board[row][i])
        tmp = tmp[::-1]
        sliding(tmp, N)
        tmp = tmp[::-1]
        for i in range(N):
            board[row][i] = tmp[i]

def slide_board(board, N, dir):
    if dir == 0:
        slide_up(board, N)
    elif dir == 1:
        slide_down(board, N)
    elif dir == 2:
        slide_left(board, N)
    else:
        slide_right(board, N)

def getMaxValue(board, N):
    ret = 0
    for i in range(N):
        for j in range(N):
            ret = max(ret, board[i][j])
    return ret

def board_copy(board, N):
    n_board = [[0 for _ in range(N)] for _ in range(N)]
    for i in range(N):
        for j in range(N):
            n_board[i][j] = board[i][j]
    return n_board

def isChange(board, n_board, N):
    for i in range(N):
        for j in range(N):
            if board[i][j] != n_board[i][j]:
                return True
    return False

def dfs(board, N, step, max_val):
    if step == 5:
        global answer
        answer = max(answer, max_val)
        return 
    for dir in range(4):
        n_board = board_copy(board, N)
        slide_board(n_board, N, dir)
        if not isChange(board, n_board, N):
            continue
        max_val = max(max_val, getMaxValue(n_board, N))
        dfs(n_board, N, step + 1, max_val)


N = int(input())
board = []
for _ in range(N):
    board.append([int(x) for x in input().split()])

answer = getMaxValue(board, N)
dfs(board, N, 0, answer)
print(answer)