문제 바로가기

2048

흔히 아는 2048 게임을 기반으로 하는 문제이다.
한 번에 상하좌우 중 한 방향으로 이동할 수 있으며, 최대 5번의 이동에서 얻을 수 있는 가장 큰 블록 값을 반환한다. 다만 게임과는 달리 매 이동에서 새로운 블록이 추가되지는 않는다.

import sys
from typing import List


class Solution:
    def __init__(self, n: int, board: List[List[int]]) -> None:
        self.n = n
        self.board = board
        self.answer = 0

    def solve(self, board: List[List[int]], count: int = 0) -> None:
        self.answer = max(self.answer, *sum(board, []))
        if count == 5:
            return
        for d in range(4):  # 4방향으로 이동한다.
            moved_board = self.move(board, d)
            self.solve(moved_board, count + 1)

    def move(self, board: List[List[int]], direction: int) -> List[List[int]]:
        """
        상/하/좌/우로 각 행 혹은 열의 블록들을 이동시키고, 같은 숫자 블록의 충돌시 합쳐준다.
        """
        n = self.n
        moved_board = None
        if direction < 2:  # 위, 아래
            moved_board = [[0] * n for _ in range(n)]
            for c in range(n):
                cur_rows = [board[r][c] for r in range(n) if board[r][c] > 0]  # 현재 열의 블록들
                if direction == 1:  # 아래 방향은 역순으로 충돌된다.
                    cur_rows.reverse()
                merged = self.merge(cur_rows)  # 같은 블록 합치기
                # 이동한 자리에 결과 반영
                if direction == 0:
                    for i in range(len(merged)):
                        moved_board[i][c] = merged[i]
                else:  # 아래 방향은 역순으로 계산했으므로 끝에서부터 반영
                    for i in range(len(merged)):
                        moved_board[n - 1 - i][c] = merged[i]
        else:  # 왼쪽, 오른쪽
            moved_board = []
            for r in range(n):
                cur_cols = list(filter(lambda x: x > 0, board[r]))  # 현재 행의 블록들
                if direction == 3:  # 오른 방향은 역순으로 충돌된다.
                    cur_cols.reverse()
                merged = self.merge(cur_cols)
                # 여백에 0 채워넣기
                merged.extend([0 for _ in range(n - len(merged))])
                if direction == 3:  # 반영 전 오른 방향은 역순으로 계산한것을 되돌려준다.
                    merged.reverse()
                # 새 보드에 반영
                moved_board.append(merged)

        return moved_board

    def merge(self, blocks: List[int]) -> List[int]:
        """
        블록을 순차적으로 순회하며 이전 블록과 현재 블록이 다르면 결과 리스트에
        넣고, 같으면 삽입한 이전 블록의 값을 두 배로 만든다.
        """
        res = []
        prev_merged = False
        for block in blocks:
            if not res or block != res[-1] or prev_merged:
                res.append(block)
                prev_merged = False
            else:
                res[-1] *= 2
                prev_merged = True
        return res


if __name__ == "__main__":
    (n,) = map(int, sys.stdin.readline().split())
    board = list()
    for i in range(n):
        board.append(list(map(int, sys.stdin.readline().split())))

    solution = Solution(n, board)
    solution.solve(solution.board)
    print(solution.answer)