백준_12100_2048 (Easy)

문제

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

12100번: 2048 (Easy)

풀이

1) DFS

def dfs(board, w) : 
    if w>=5 : return max(max(board, key = max))
    
    return max(solve(up(board), w+1), 
               solve(down(board), w+1), 
               solve(right(board), w+1), 
               solve(left(board), w+1))

2) 블록 오른쪽으로 밀기

각 행을 떼어내서 아래처럼 연산한다. 여기서 주의할 점은 두가지이다.

(1) value 값이 같으면 새로운 first 값을 뽑아야 하고, 그렇지 않으면 이전의 second 값을 가져다 쓴다.

(2) 0은 빈칸을 의미하므로, 무시한다.

3) 블록 아래로 밀기

위와 마찬가지로, 한 열씩 떼어내어 연산한다.

4) 블록 왼쪽, 위로 밀기

왼쪽으로 밀기 위해서 2) 오른쪽으로 밀기를 이용한다.

위로 밀기 위해서 3) 아래로 밀기를 이용한다.

코드

# find next number (not 0)
def find(stack) :
    while stack : 
        number = stack.pop()
        if number!=0 : return number
    return 0

def right(board) : 
    newBoard = [[0 for j in range(N)] for i in range(N)]
    for i in range(N) : 
        # get object
        stack = [board[i][j] for j in range(N)]
            
        # summary
        queue = list()
        while True : 
            first = find(stack)
            second = find(stack)
            if first==0 and second==0 : break
            if first==None : break
            if first==second : 
                queue.append(first+second)
            else : 
                queue.append(first)
                stack.append(second) # 하나 집어 넣기
        
        # fill board
        blank = N-len(queue)
        for j in range(len(queue)) : 
            if not queue: break
            else : newBoard[i][blank+j] = queue.pop()  
    return newBoard

def left(board) : 
    newBoard = [board[i][::-1] for i in range(N)]
    newBoard = right(newBoard)
    return [newBoard[i][::-1] for i in range(N)]

def down(board) : 
    newBoard = [[0 for j in range(N)] for i in range(N)]
    for j in range(N) : 
        # get object
        stack = [board[i][j] for i in range(N)]
            
        # summary
        queue = list()
        while True : 
            first = find(stack)
            second = find(stack)
            if first==0 and second==0 : break
            if first==None : break
            if first==second : 
                queue.append(first+second)
            else : 
                queue.append(first)
                stack.append(second) # 하나 집어 넣기
            
        # fill board
        blank = N-len(queue)
        for i in range(len(queue)) : 
            if not queue: break
            else : newBoard[i+blank][j] = queue.pop()  
    return newBoard

def up(board) : 
    newBoard = board[::-1]
    newBoard = down(newBoard)
    return newBoard[::-1]

def solve(board, w) : 
    if w>=5 : return max(max(board, key = max))
    
    return max(solve(up(board), w+1), 
               solve(down(board), w+1), 
               solve(right(board), w+1), 
               solve(left(board), w+1))

import sys
input = sys.stdin.readline
N = int(input().strip())
board = [list(map(int, input().strip().split())) for i in range(N)]
ans = solve(board, 0)
print(ans)