[Python] BOJ 12100 - 2048(Easy)

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

12100번: 2048 (Easy)

# 2016년 하반기 삼성 SW역량테스트문제이다. 

# 제목은 Easy인데, 전혀 Easy하지 않다..

 

 

# 보드의 크기가 최대 20이고 최대 5번이동할 수 있으므로 각각 상하좌우로 5번 시뮬레이션 돌려도

   20 * 20 * 4^5 = 40만번이므로 시간초과가 나지 않을 것이라 생각했다.

 

# 우선 구현하는 데 있어서 중요한 과정 몇가지가 있다.

    * 한 번 이동할때 모든 블록이 그 방향 벽으로 다 붙기때문에 이 과정을 구현해야한다.

    * 똑같은 수가 3개가 있는 경우에는 이동하려고 하는 쪽의 칸이 먼저 합쳐진다.

    * 재귀를 통해 상하좌우로 5번 시뮬레이션 돌리기 구현

 

 

1. BT함수: cnt가 5가 되었을 때, 블록중의 최댓값을 찾아서 mx에 넣어준다.

                시뮬레이션 돌리기 전 block을 copy해서 b에 할당해준 뒤 반복문을 통해

                recur함수와 BT(cnt+1)을 실행해준다.

                block에 b를 다시 copy해서 넣어준다.

 

2. recur함수: dir에 따라서 상하좌우로 시뮬레이션을 돌려준다.

         2-1. 먼저 한번 이동시킬 때 모든 블록을 끝쪽으로 몰아주기 위해서 p라는 새로운 배열을 만들었다.

                  위로 이동하는 경우 (dir == 1) 각 열마다 반복문을 돌며 위에서부터 0이 아닌값을 만나면

                  p에 append해준다. 그리고 하나의 열을 다 돌았으면 p뒤에 0을 N-len(p)만큼 더해준다. 

                  그 뒤 다시 해당하는 열의 1행부터 하나하나 p의 값으로 갱신해준다. 

           

           ex) 어떤 배열이 [2, 0, 0, 2, 0, 2, 2, 2]가 있다고 치면, 왼쪽부터 2를 만날때마다 p에 2를 넣어준다.

                p에는 [2, 2, 2, 2, 2]가 들어가있고 N-len(p)해주면 0의 개수가 나오므로 최종적으로

                p는 [2, 2, 2, 2, 2, 0, 0, 0]이 된다. 즉 처음 배열의 수들을 모두 왼쪽으로 몰아준 형태이다.

 

        2-2. 한쪽 끝으로 다 몰아줬으면 이제 블록끼리 합치는 작업을 해야한다.

                 dir이 1인경우, 위에서 부터 합쳐야 하므로 1행부터 아래로 내려가며 위 아래 숫자가 같은지

                 확인한다. 같으면 윗칸을 두배 해준뒤 아래아래 칸부터 위로 한칸씩 옮겨준다.

                 그리고 맨 아래칸을 0으로 바꿔준다.

 

import sys, copy
input = sys.stdin.readline
sys.setrecursionlimit(10**9)
N = int(input())
mx = 0
block = [list(map(int,input().split())) for _ in range(N)]
# dir : 상 하 좌 우 / 1 2 3 4
def recur(dir):

    if dir == 1:
        for i in range(N):
            p = []
            for j in range(N):
                if block[j][i] != 0:
                    p.append(block[j][i])

            p += [0] * (N - len(p))
            for j in range(N):
                block[j][i] = p[j]
        
        for i in range(N-1):
            for j in range(N):
                if block[i+1][j] == block[i][j]:
                    block[i][j] = block[i+1][j] * 2
                    for k in range(i+1, N-1):
                        block[k][j] = block[k+1][j]
                    block[-1][j] = 0

    if dir == 2:
        for i in range(N):
            p = []
            for j in range(N):
                if block[j][i] != 0:
                    p.append(block[j][i])

            p = [0] * (N - len(p)) + p
            for j in range(N):
                block[j][i] = p[j]

        for i in range(N-1, 0, -1):
            for j in range(N):
                if block[i][j] == block[i-1][j]:
                    block[i][j] = block[i-1][j] * 2
                    for k in range(i-1, 0, -1):
                        block[k][j] = block[k-1][j]
                    block[0][j] = 0

    if dir == 3:
        for i in range(N):
            p = []
            for j in range(N):
                if block[i][j] != 0:
                    p.append(block[i][j])

            p += [0] * (N - len(p))
            for j in range(N):
                block[i][j] = p[j]
                        
        for i in range(N):
            for j in range(N-1):
                if block[i][j] == block[i][j+1]:
                    block[i][j] = block[i][j] * 2
                    for k in range(j+1, N-1):
                        block[i][k] = block[i][k+1]
                    block[i][-1] = 0

    if dir == 4:
        for i in range(N):
            p = []
            for j in range(N):
                if block[i][j] != 0:
                    p.append(block[i][j])

            p = [0] * (N - len(p)) + p
            for j in range(N):
                block[i][j] = p[j]

        for i in range(N):
            for j in range(N-1, 0, -1):
                if block[i][j] == block[i][j-1]:
                    block[i][j] = block[i][j-1] * 2
                    for k in range(j-1, 0, -1):
                        block[i][k] = block[i][k-1]
                    block[i][0] = 0

def BT(cnt):
    global block, mx
    if cnt == 5:
        for i in range(N):
            for j in range(N):
                if block[i][j] > mx:
                    mx = block[i][j]
        return

    b = copy.deepcopy(block)
    for i in range(1, 5):
        recur(i)
        BT(cnt+1)
        block = copy.deepcopy(b)

BT(0)
print(mx)

(solved.ac 티어: 골드 2)

 

# 백트래킹이랑 재귀에 약해서 그런지 문제푸는데 매우 오래걸렸다..