[221010] 백준 12100 : 2048(Easy)

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

12100번: 2048 (Easy)

1. 상, 하, 좌, 우 통합

 상, 하, 좌, 우를 전부 구현하기에는 힘들다. 그럴 바에 상, 하의 경우는 90도 시계 방향으로 돌려서 동일하게 계산시키자. 이렇게만 해도 짜야될 코드가 2개는 줄어든다. 아래의 그림을 보자

 

 다음과 같이 돌려서 생각한다면, 위쪽 방향으로 미는 것은 오른쪽 방향으로 미는 것과 같고, 아래쪽 방향으로 미는 것은 왼쪽 방향으로 미는 것과 같다. 파이썬에서는 배열을 시계방향으로 90도 돌릴 수 있는 훌륭한 한 줄짜리 코드가 있다.

temp = list(map(list, zip(*arr[::-1])))

 

위의 코드 한 줄이면 배열을 쉽게 돌릴 수 있다. 4번 돌리면 원래대로 돌아오니 충분히 응용할 수 있다. 

2. 밀 때 주의할 점!

 문제에서 한 번의 이동에서 이미 합쳐진 블록은 또 합쳐질 수 없다고 했다. 다음과 같은 경우를 보자.

위의 배열에서 왼쪽으로 민다고 생각해보자. 주황색으로 표시된 것은 계산이 완료된 상황이고, 파란색으로 표시된 것은 이제 계산을 해야 되는 부분이다. 첫 번째 그림은 3행 2열이 3행 1열과 만나 합쳐진 결과이고, 두 번째 사진은 3행 2열로 붙었다. 반복해서 계산하다 보면 4번째 그림과 같이 된다.(우측 하단)

따라서, 먼저 계산했을 때 합산된 결과에 대해서 Check = True 값을 주고, False인 경우에만 합칠 수 있도록 한다. 다시 말해서, 첫 번째 그림(좌측 상단)에서는 Check = False 이므로 합산이 되고, 두 번째(우측 상단)에서는 숫자는 같지만, Check = True이기 때문에 합쳐지지 않고 그대로 다음으로 넘어간다. 그리고 다시 Check = False를 주고 반복하면 4번째 그림과 같이 되는 것이다.

3. 전체 코드

메모리 : 119088 KB, 시간 : 516 ms, 풀이 시간 : 120 min

N = int(input())
board = [list(map(int, input().split())) for _ in range(N)]
dx = [-1, 1]
def move(d):
    # d == left or right
    if d == 0 :
        for i in range(N):
            temp = board[i]
            check = False
            for j in range(1, len(temp)):
                if temp[j] != 0 :
                    x = j
                    while True :
                        nx = x + dx[d]
                        if 0 <= nx < N :
                            if temp[nx] == 0 :
                                temp[nx] = temp[x]
                                temp[x] = 0
                                x = nx
                            else :
                                if temp[nx] == temp[x] and not check:
                                    temp[nx] += temp[x]
                                    temp[x] = 0
                                    check = True
                                    break
                                else :
                                    check = False
                                    break
                        else :
                            break
            for j in range(len(temp)):
                board[i][j] = temp[j]
    elif d == 1 :
        for i in range(N):
            temp = board[i]
            check = False
            for j in range(len(temp)-2, -1, -1):
                if temp[j] != 0 :
                    x = j
                    while True :
                        nx = x + dx[d]
                        if 0 <= nx < N :
                            if temp[nx] == 0 :
                                temp[nx] = temp[x]
                                temp[x] = 0
                                x = nx
                            else :
                                if temp[nx] == temp[x] and not check:
                                    temp[nx] += temp[x]
                                    temp[x] = 0
                                    check = True
                                    break
                                else :
                                    check = False
                                    break
                        else : break
            for j in range(len(temp)):
                board[i][j] = temp[j]

def rotate(d, arr):
    # 90도 회전
    if d == 2 : d = 1
    if d == 3 : d = 0
    temp = list(map(list, zip(*arr[::-1])))
    for i in range(N):
        for j in range(N):
            board[i][j] = temp[i][j]
    return d

def recover(arr):
    for _ in range(3):
        arr = list(map(list, zip(*arr[::-1])))
    for i in range(N):
        for j in range(N):
            board[i][j] = arr[i][j]
def solve() :
    direction = [0, 1, 2, 3] # 좌, 우, 상, 하
    case = []
    maxValue = 0
    for n1 in direction :
        for n2 in direction :
            for n3 in direction :
                for n4 in direction :
                    for n5 in direction :
                        case.append([n1, n2, n3, n4, n5])
    while case :
        [n1, n2, n3, n4, n5] = case[0]
        del case[0]
        temp = [[x for x in arr] for arr in board]
        for m in [n1, n2, n3, n4, n5] :
            if m == 2 or m == 3 :
                m = rotate(m, board)
                move(m)
                recover(board)
            else :
                move(m)
        for i in range(N):
            maxValue = max(maxValue, max(board[i]))

        for i in range(N):
            for j in range(N):
                board[i][j] = temp[i][j]

    print(maxValue)

solve()