[백준] 12100번: 2048 (Easy)

문제

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

12100번: 2048 (Easy)

 

풀이

큐를 이용해 행 혹은 열에서 0이 아닌 값들을 저장해놓는다.

board의 크기만큼 반복문을 돌며

1. 큐의 길이가 2이상인 경우에 앞 혹은 뒤의 두 숫자가 같으면 pop() + pop() 값을
2. 위의 조건이 성립하지 않은 경우 큐가 남아 있다면 pop() 값을
3. 큐가 비어있다면 0을

board에 저장한다.

DFS를 활용해 모든 경우의 수를 탐색하며 가장 큰 값을 저장한다.

DFS 함수에서 deepcopy()를 사용해 함수를 거친 board 값이 다음 함수에 들어가지 않도록 해줘야 한다.

 

코드

import sys
from collections import deque
from copy import deepcopy

result = 0
n = int(sys.stdin.readline())
board = []

for _ in range(n):
    board.append(list(map(int, sys.stdin.readline().split())))

def move(board, dir):
    if dir == 0:    # 위쪽으로 이동
        for i in range(n):
            queue = deque([board[j][i] for j in range(n) if board[j][i] != 0])
            for j in range(n):
                if len(queue) > 1 and queue[0] == queue[1]:
                    board[j][i] = queue.popleft() + queue.popleft()
                else:
                    board[j][i] = queue.popleft() if queue else 0
    elif dir == 1:  # 아래쪽으로 이동
        for i in range(n):
            queue = deque([board[j][i] for j in range(n) if board[j][i] != 0])
            for j in range(n)[::-1]:
                if len(queue) > 1 and queue[-1] == queue[-2]:
                    board[j][i] = queue.pop() + queue.pop()
                else:
                    board[j][i] = queue.pop() if queue else 0
    elif dir == 2:  # 왼쪽으로 이동
        for i in range(n):
            queue = deque([x for x in board[i] if x != 0])
            for j in range(n):
                if len(queue) > 1 and queue[0] == queue[1]:
                    board[i][j] = queue.popleft() + queue.popleft()
                else:
                    board[i][j] = queue.popleft() if queue else 0
    elif dir == 3:  # 오른쪽으로 이동
        for i in range(n):
            queue = deque([x for x in board[i] if x != 0])
            for j in range(n)[::-1]:
                if len(queue) > 1 and queue[-1] == queue[-2]:
                    board[i][j] = queue.pop() + queue.pop()
                else:
                    board[i][j] = queue.pop() if queue else 0
    return board

def DFS(board, L):
    global result
    if L == 5:
        result = max(result, max(map(max, board)))
        print(board)
    else:
        for i in range(4):
            DFS(move(deepcopy(board), i), L + 1)

DFS(board, 0)
print(result)