12100. 2048 (Easy)

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

 

 

4개의 방향을 중복 순열로 가능한 가짓수를 모두 뽑아서(4^5) 각각 이동을 시키는 방법(n^2)으로 풀었다. 

BFS,DFS로 푸는 방법도 있던데 이 방법은 완전탐색에 가까운 것 같다.

import sys
import collections
from copy import deepcopy
WEST, EAST, NORTH, SOUTH = 1, 2, 3, 4


def Print(lst):
    for i in lst:
        for j in i:
            print(j, end=" ")
        print("")
    print("")


def move_north(board):
    queue = collections.deque()
    joinable = [[True for _ in range(n)] for _ in range(n)]  # 한번 합쳐진 블록은 False로 표시
    
    # 작업할 큐를 만듦
    for row in range(n):
        for col in range(n):
            if board[row][col] != 0:  # 0이 아니면 추가
                queue.append([row, col])
            else:  # 0이면 0이 아닌 값을 땡겨와서 추가
                for sub_row in range(row+1, n):
                    if board[sub_row][col] != 0:
                        board[row][col] = board[sub_row][col]
                        board[sub_row][col] = 0
                        queue.append([row, col])
                        break

    while queue:
        row, col = queue.popleft()
        if 0 <= row + 1 < n:
            if board[row][col] == 0 and board[row+1][col] != 0:  # 처음에는 0이 아니었지만 합쳐지면서 0이 된 경우
                board[row][col] = board[row+1][col]  # row+1을 땡겨온다. joinable도 땡겨옴
                board[row+1][col] = 0
                joinable[row][col] = joinable[row+1][col]
                joinable[row+1][col] = True
                if joinable[row][col]:
                    queue.append([row, col])
            elif board[row][col] == board[row+1][col]:  # 합침
                board[row][col] = board[row][col]*2
                board[row+1][col] = 0
                joinable[row][col] = False


def move_south(board):
    queue = collections.deque()
    joinable = [[True for _ in range(n)] for _ in range(n)]
    for row in reversed(range(0, n)):
        for col in range(0, n):
            if board[row][col] != 0:
                queue.append([row, col])
            else:
                for sub_row in reversed(range(0, row)):
                    if board[sub_row][col] != 0:
                        board[row][col] = board[sub_row][col]
                        board[sub_row][col] = 0
                        queue.append([row, col])
                        break

    while queue:
        row, col = queue.popleft()
        if 0 <= row - 1 < n:
            if board[row][col] == 0 and board[row-1][col] != 0:  # 처음에는 0이 아니었지만 합쳐지면서 0이 된 경우
                board[row][col] = board[row-1][col]
                board[row-1][col] = 0
                joinable[row][col] = joinable[row-1][col]
                joinable[row-1][col] = True
                if joinable[row][col]:
                    queue.append([row, col])
            elif board[row][col] == board[row-1][col]:
                board[row][col] = board[row][col]*2
                board[row-1][col] = 0
                joinable[row][col] = False


def move_east(board):
    queue = collections.deque()
    joinable = [[True for _ in range(n)] for _ in range(n)]
    for row in range(n):
        for col in reversed(range(0, n)):
            if board[row][col] != 0:
                queue.append([row, col])  # board[row][col][1] = True
            else:  # 값이 0이면 땡겨오고나서 큐에 추가
                for sub_col in reversed(range(0, col)):
                    if board[row][sub_col] != 0:
                        board[row][col] = board[row][sub_col]
                        board[row][sub_col] = 0
                        queue.append([row, col])
                        break

    while queue:
        row, col = queue.popleft()
        if 0 <= col-1 < n:
            if board[row][col] == 0 and board[row][col-1] != 0:  # 처음에는 0이 아니었지만 합쳐지면서 0이 된 경우
                board[row][col] = board[row][col-1]
                board[row][col-1] = 0
                joinable[row][col] = joinable[row][col-1]
                joinable[row][col-1] = True
                queue.append([row, col])
            elif board[row][col] == board[row][col-1]:
                board[row][col] = board[row][col]*2
                board[row][col-1] = 0
                joinable[row][col] = False
                joinable[row][col-1] = True


def move_west(board):
    queue = collections.deque()
    joinable = [[True for _ in range(n)] for _ in range(n)]  # 한 번 합쳐진 블록은 False로 표시

    # 작업할 큐를 만듦
    for row in range(n):
        for col in range(n):
            if board[row][col] != 0:  # 0이 아닌 값만 큐에 추가
                queue.append([row, col])
            else:  # 값이 0이면 0이 아닌 것을 뒤에서 땡겨와서 그 값을 큐에 추가
                for sub_col in range(col+1, n):
                    if board[row][sub_col] != 0:
                        board[row][col] = board[row][sub_col]
                        board[row][sub_col] = 0
                        queue.append([row, col])
                        break

    while queue:
        row, col = queue.popleft()
        if 0 <= col+1 < n:
            if board[row][col] == 0 and board[row][col+1] != 0:  # 처음에는 0이 아니었지만 합쳐지면서 0이 된 경우
                board[row][col] = board[row][col+1]
                board[row][col+1] = 0
                joinable[row][col] = joinable[row][col+1]
                joinable[row][col+1] = True
                if joinable[row][col]:
                    queue.append([row, col])
            elif board[row][col] == board[row][col+1]:
                board[row][col] = board[row][col]*2
                board[row][col+1] = 0
                joinable[row][col] = False
                joinable[row][col+1] = True


###
# 중복 순열에 뽑힌 방향 순서대로 보드를 이동시키는 함수
###
def move(directions):
    global maxValue
    board = deepcopy(board_origin)  # 원본 보드가 변경되면 안되므로 deepcopy 필요

    for way in directions:
        if way == WEST:
            move_west(board)
        elif way == EAST:
            move_east(board)
        elif way == NORTH:
            move_north(board)
        elif way == SOUTH:
            move_south(board)

    # 최댓값 비교
    for line in board:
        maxValue = max(maxValue, max(line))


###
# 동서남북을 중복을 허용하면서 재귀적으로 5가지를 뽑은 후
# count가 5가 되면 그 방향대로 이동을 시작시키는 함수
###
def get_permutation_directions(count, selected):
    if count == 5:
        move(selected)
        return

    for way in [WEST, EAST, NORTH, SOUTH]:
        selected.append(way)
        get_permutation_directions(count+1, selected)
        selected.pop()


if __name__ == '__main__':
    maxValue = 0
    n = int(sys.stdin.readline())

    board_origin = []
    for _ in range(n):
        board_origin.append(list(map(int, sys.stdin.readline().split())))

    get_permutation_directions(0, [])

    print(maxValue)