[백준 12100] 2048 (Easy)

문제 보기

이 문제도 BFS와 브루트 포스를 합친 문제이다.

처음에 문제를 읽었을 때, 완전탐색을 해야하지만 무엇을 완전탐색 해야할 지 감이 잡히지 않았다.

계속 고민을 하다보니, 상, 하, 좌, 우로 블록들을 이동시켰을 때의 판의 상태를 완전탐색해야겠다고 생각했다.

BFS 부분은 그래프 내에서 최대값을 구하는 알고리즘과 동일하다.

구현 상의 어려운 부분은 moveBoard 메소드인데, 블록들을 이동시켰을 때의 상태를 새로운 판 객체로 반환해서, 이를 큐에 추가하는 것이다.

문제는 최대 5번 이동시켜서 얻을 수 있는 최댓값을 구하는 것이기 때문에, 5번이 넘어가면 BFS를 중단하고 결과값을 반환한다.

판 객체를 큐에 추가한다는 개념은 아래의 그림을 보면 이해하기 쉽다.

위 그림은 블록들을 1번 이동시켰을 때의 상태이며, 각 UP, RIGHT, DOWN, LEFT마다 다시 각 방향으로 블록들을 이동시키고, 이를 5번까지 반복한다.

판 위의 블록들을 이동시키는 메소드는 moveBoard()이며, 구현 방법은 주석을 참고하면 된다.

import sys
from queue import Queue
from copy import deepcopy
 
n = int(sys.stdin.readline())
board = [list(map(int, sys.stdin.readline().split())) for r in range(n)]
 
 
def moveBoard(direction, original_board):
    ret = 0
    temp_board = deepcopy(original_board)
    block_list = list()
    
    # up
    if direction == 0:
        for j in range(n):
            for i in range(n - 1, -1, -1):
                # add non-zero blocks to the stack from the bottom
                if temp_board[i][j] != 0:
                    block_list.append(temp_board[i][j])
                    temp_board[i][j] = 0
                
            # merge continuous same blocks in the list
            length = len(block_list)
            idx = length - 1
            while idx > -1:
                if idx > 0:
                    if block_list[idx] == block_list[idx - 1]:
                        block_list[idx - 1:idx + 1] = [block_list[idx] * 2]
                        length -= 1
                    else:
                        idx += 1
                idx -= 2
            
            # arrange blocks in the list from the top
            idx = 0
            while block_list:
                temp_board[idx][j] = block_list.pop()
                idx += 1
    # right
    elif direction == 1:
        for i in range(n):
            for j in range(n):
                # add non-zero blocks to the stack from the left
                if temp_board[i][j] != 0:
                    block_list.append(temp_board[i][j])
                    temp_board[i][j] = 0
            
            # merge continuous same blocks in the list
            length = len(block_list)
            idx = length - 1
            while idx > -1:
                if idx > 0:
                    if block_list[idx] == block_list[idx - 1]:
                        block_list[idx - 1:idx + 1] = [block_list[idx] * 2]
                        length -= 1
                    else:
                        idx += 1
                idx -= 2
            
            # arrange blocks in the list from the right
            idx = n - 1
            while block_list:
                temp_board[i][idx] = block_list.pop()
                idx -= 1
    # down
    elif direction == 2:
        for j in range(n):
            for i in range(n):
                # add non-zero blocks to the stack from the top
                if temp_board[i][j] != 0:
                    block_list.append(temp_board[i][j])
                    temp_board[i][j] = 0
            
            # merge continuous same blocks in the list
            length = len(block_list)
            idx = length - 1
            while idx > -1:
                if idx > 0:
                    if block_list[idx] == block_list[idx - 1]:
                        block_list[idx - 1:idx + 1] = [block_list[idx] * 2]
                        length -= 1
                    else:
                        idx += 1
                idx -= 2
            
            # arrange blocks in the list from the bottom
            idx = n - 1
            while block_list:
                temp_board[idx][j] = block_list.pop()
                idx -= 1
    # left
    else:
        for i in range(n):
            for j in range(n - 1, -1, -1):
                # add non-zero blocks to the stack from the right
                if temp_board[i][j] != 0:
                    block_list.append(temp_board[i][j])
                    temp_board[i][j] = 0
            
            # merge continuous same blocks in the list
            length = len(block_list)
            idx = length - 1
            while idx > -1:
                if idx > 0:
                    if block_list[idx] == block_list[idx - 1]:
                        block_list[idx - 1:idx + 1] = [block_list[idx] * 2]
                        length -= 1
                    else:
                        idx += 1
                idx -= 2
            
            # arrange blocks in the list from the left
            idx = 0
            while block_list:
                temp_board[i][idx] = block_list.pop()
                idx += 1
    
    # find maximum block
    for i in range(n):
        for j in range(n):
            if temp_board[i][j] > ret:
                ret = temp_board[i][j]
    return temp_board, ret
 
 
def solution():
    q = Queue()
    q.put((board, 0))
    visited = list()
    answer = 0
    
    while q.qsize() > 0:
        original_board, count = q.get()
        
        if count > 4:
            return answer
        
        for i in range(4):
            temp_board, ret = moveBoard(i, original_board)
            
            if ret > answer:
                answer = ret
            
            if temp_board not in visited:
                q.put((temp_board, count + 1))
        visited.append(original_board)
        
    return answer
 
 
print(solution())