12100번 - 2048(Easy)

문제

12100번: 2048 (Easy) (acmicpc.net)

12100번: 2048 (Easy)

풀이 1

슬라이드를 최대  5번 해서 얻을 수 있는 가장 큰 블록을 출력해야 하는 문제이다.

가장 큰 값 찾기

가장 먼저 알아차려야 하는 것은, 슬라이드를 한 후의 가장 크기가 큰 블록은 이전 상태의 가장 크기가 큰 블록보다 같거나 크다는 것이다. 따라서 슬라이드를 5번까지 한 4^5 = 1024개의 보드들의 숫자들을 전부 탐색하며 최대값을 찾아내면 되고, 그 연산량은 1024*400 = 409,600 이 된다.

상태 갱신

BFS를 이용해 4->4^2->4^3->4^4->4^5 순서로 보드의 상태를 갱신하므로, 슬라이드 횟수가 5가 될때는 가장 큰 값 찾기에 포함되는 연산인 것을 감안하면 상태 갱신 연산량은 총 340이 된다. 20,000,000 ~100,000,000 정도를 최대 연산량으로 잡았을 때, (한개의 보드 갱신 연산) * 340 < 100,000,000 이 되어야 하므로 보드 갱신은 O(N^2) 의 시간복잡도 까지 허용된다는 것을 짐작 가능하다.

보드 갱신

큰 구조는 매우 간단한 구조이나, 사실 이 문제에서 관건이 되는 부분은 슬라이드를 구현하는 것이다. 현재 보드 상태와 슬라이드 방향을 받은 뒤, 슬라이싱을 이용해 슬라이드 방향대로 보드를 탐색한다. 이때, 슬라이드 방향이 위 아래라면 보드를 전치해줘야 한다. 한 행씩 탐색하며 서로 다른값이거나 new_row가 비어있다면 값을 넣어주고, 만약 같은 값이 연속으로 나온다면 해당 값에 2를 곱해준다. 이 때 한번 2를 곱해준 요소는 다시 2를 곱하면 안되므로, 음수를 곱해줘서 여러번 값이 합쳐지는것을 방지한다. 슬라이드가 끝난 뒤 새로운 보드를 반환할 때도 전치를 했다면 다시 전치를 하고, 탐색 방향이 역방향이라면 해당 방향대로 다시 돌려주어야 한다.

from collections import deque

n = int(input())

board = []

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

dRow = [-1,0,1,0]
dCol = [0,-1,0,1]

def slide_board(_board,vector):
    result = []
    step = -sum(vector)
    # 상하 방향 이면 전치
    if vector[0] != 0:
        _board = list(zip(*_board))
    for nums in _board:
        new_row = []
        for num in nums[::step]:
            if num != 0:
                if not new_row or num != new_row[-1]:
                    new_row.append(num)
                else:
                    new_row[-1] *= -2
        while len(new_row) < n:
            new_row.append(0)
        result.append(list(map(abs,new_row[::step])))
    return result if vector[0] == 0 else list(map(list,zip(*result)))

answer = -int(1e9)
q = deque()
q.append((board,0))

while q:
    _board,cnt = q.popleft()
    new_board = [[*elem] for elem in _board]
    for i in range(4):
        if cnt < 5:
            q.append((slide_board(new_board,(dRow[i],dCol[i])),cnt+1))
        else:
            for elem in _board:
                answer = max(answer,max(elem))

print(answer)

풀이 2

문제에서 최대 5번 까지 슬라이드를한 후 가장 최대값을 갖는 블럭을 찾으라고 하지만, 블럭의 숫자가 나눠질일은 없으므로 그냥 5번째 슬라이드에서 보드에서의 최대값을 찾아 answer를 갱신하면 된다.

위 방법보다 좀 더 단순한 방법으로 접근했는데, 보드를 계속해서 90도씩 돌려가며 백트래킹을 하는것이다. 보드의 탐색 방향을 바꾸는것이 아니고, 탐색 방향은 왼쪽->오른쪽, 위->아래로 고정하되 보드 자체를 90도씩 돌려가며 DFS를 진행했다. 또 조건 중에 이미 한번 합쳐진 블럭은 다시 합쳐지면 안된다는 조건이 있는데, 블럭을 쌓을 때 visited로 상태를 따로 체크하면 된다.

N = int(input())
board = []
for row in range(N):
    board.append(list(map(int,input().split())))


def rotate_ccw_90(mat):
    new_mat = [[0]*N for _ in range(N)]
    for row in range(N):
        for col in range(N):
            new_mat[row][col] = mat[col][N-row-1]
    return new_mat


def get_answer(cnt):
    global answer,board
    if cnt >= 5:
        for row in range(N):
            for col in range(N):
                if board[row][col] > answer:
                    answer = board[row][col]
        return


    for i in range(4):
        cpy_board = [[*elem] for elem in board]
        new_board = [[] for _ in range(N)]
        visited = [[] for _ in range(N)]
        # 블럭 쌓으면서 합치기
        for row in range(N):
            for col in range(N):
                if board[row][col] > 0:
                    if new_board[row] and visited[row][-1] == 0 and board[row][col] == new_board[row][-1]:
                        visited[row][-1] = 1
                        new_board[row][-1] *= 2
                    else:
                        visited[row].append(0)
                        new_board[row].append(board[row][col])
        # 빈 칸 채우기
        for row in range(N):
            while len(new_board[row]) < N:
                new_board[row].append(0)
        board = [[*elem] for elem in new_board]
        get_answer(cnt+1)
        board = rotate_ccw_90(cpy_board)


answer = 0
get_answer(0)
print(answer)