[BOJ] 12100번 2048 (Easy) (Python) [삼성 SW 역량 테스트 기출 문제]

문제

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

풀이

AC받기까지 1시간 20분 정도 소요되었다.

• 문제를 읽으면서 작은 문제로 만드는 과정을 통하니 문제가 쉽게 접근되었다. 2차원이 아닌 1차원에서 한쪽으로 미는 상황에 대한 함수를 빼서 구현했다.
• 문제에서 N의 최대값이 20이어서 시간복잡도가 안좋게 나오겠다고 예상했다. 내 코드를 기반으로 $O(4^5*(20^2))$이 나왔다. 여기서 4는 4가지 방향, 20은 보드의 크기이다.
• 문제에서 테케가 1개밖에 없어서 스스로 많이 만들어봤다. 근데, 큰 수에 대한 테스크 케이스는 수동으로 넣기 힘들어서 이런 경우 코드로 직접 테스트 케이스를 만들어줘야 할지가 고민이다.
• itertools에 permutaions를 적용하는데 빈 리스트가 나와서 삽질했는데, 순열이 아닌 중복순열을 이용하므로 product를 이용해야 했다.

from itertools import product
from copy import deepcopy

UP, DOWN, LEFT, RIGHT = 0, 1, 2, 3


def move_left(one_list):  # one_list를 왼쪽으로 밈
    merged = [False] * len(one_list)  # 합쳐진 블록인지 여부

    for i in range(1, len(one_list)):  # 왼쪽부터 하니씩 왼쪽으로 땡기기(1, 2, ..., N-1)
        reach_end = True

        for j in reversed(range(i)):  # i-1, i-2, ..., 0
            if one_list[j] == 0:  # 빈칸
                continue
            elif one_list[j] == one_list[i] and not merged[j]:  # 합치기
                one_list[j] *= 2
                merged[j] = True
                one_list[i] = 0
                reach_end = False
                break  #옮겼으니 탈출
            else:  # 멈출 위치
                one_list[j + 1] = one_list[i]
                if j + 1 != i:  # 같을 수 있다
                    one_list[i] = 0
                reach_end = False
                break

        # 맨끝도달
        if reach_end:
            one_list[0] = one_list[i]
            one_list[i] = 0

    return one_list  # 민 결과 반환 (call by reference여서 반환값 필요하면 받기)


def board_one_move(copied_board, direction):
    if direction == UP:
        for i in range(N):  # 세로줄 하나씩
            one_list = [garo[i] for garo in copied_board]
            return_list = move_left(one_list)
            for idx, num in enumerate(return_list):
                copied_board[idx][i] = num

    elif direction == DOWN:
        for i in range(N):  # 세로줄 하나씩
            one_list = [garo[i] for garo in copied_board]
            return_list = move_left(one_list[::-1])[::-1]
            for idx, num in enumerate(return_list):
                copied_board[idx][i] = num

    elif direction == LEFT:
        for i in range(N):  # 가로줄 하나씩
            move_left(copied_board[i])

    else:  # RIGHT
        for i in range(N):  # 가로줄 하나씩
            copied_board[i] = move_left(copied_board[i][::-1])[::-1]


N = int(input())  # 보드 크기
board = [list(map(int, input().split())) for _ in range(N)]
ans = -float('inf')

for directions in product([UP, DOWN, LEFT, RIGHT], repeat=5):
    copied_board = deepcopy(board)  # 보드 복제

    # 5번 이동
    for direction in directions:
        board_one_move(copied_board, direction)

    # 최대값 갱신
    for i in range(N):
        for j in range(N):
            ans = max(ans, copied_board[i][j])

print(ans)