12100_2048(easy)

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

12100번: 2048 (Easy)

 

 

2048을 구현하면 되는 문제이다.

 

결국 5번의 전체탐색을 해야하는데 이는 dfs를 사용했다.

 

그리고 위,오른쪽,아래,왼쪽으로 이동시킬때 문제를 쪼개서 생각해 보았다.

 

해당 부분을 위로 올리는 과정을 생각해보자.

 

4개의 세로줄이 있는데 이를 왼쪽부터 차례대로 하나씩 올리는 방향으로 계산을 할 것이다.

 

우선 왼쪽 상단부터 2,2,2를 순서대로 빼서 큐에 넣는다고 생각해보자.

 

그렇다면 

 

다음과같은 빈 공간이 생길것이다 여기에 2,2,2를 차례대로 넣을 것이다.

 

해당 공간을 위에서부터 a,b,c,d 공간이라고 생각해보자. 우리는 a공간부터 채워나가면 되며 경우의 수는 아래 3가지가 있다.

 

1. 공간에 아무것도 없는 경우

2. 공간에 수가 있는데 넣을수와 같은 경우

3. 공간에 수가 있고 넣을 수와 같지 않는 경우

 

1번같은 경우 2를 그대로 넣고 a공간을 그대로 검사하게 하면 된다.

2번같은 경우 합쳐질수 있으므로 2의 2배의 값을 a공간에 넣어주고 b공간을 검사하게 하면된다.(한번합치면 또합칠 수 없으므로)

3번같은 경우 a공간은 내비두고 b공간에 2를 넣어주고 b공간을 검사하게 한다.(다음수가 합쳐질 수 있으므로)

 

즉

 

-> 2          4           4

    0     ->  0  ->     2

    0          0           0

 

위와같은 형식으로 채워지게 될 것이다. 화살표는 현재 검사하고 있는 부분이다. 

 

이를 전체적으로 적용하면 문제를 해결할 수 있다.

 

 

from collections import deque

n = int(input())
board = [ list(map(int,input().split())) for _ in range(n)]
q = deque([])

dx = [ 1,0,-1,0 ]
dy = [ 0,1,0,-1 ]

def get(i,j):
    if board[i][j]:
        q.append(board[i][j])
        board[i][j]=0

def merge(i,j,k):
    while q:
        tmp = q.popleft()
        if not board[i][j]:
            board[i][j] = tmp
        elif board[i][j] == tmp:
            board[i][j] = tmp*2
            i,j = i - dy[k],j-dx[k]
        else:
            i, j = i - dy[k], j - dx[k]
            board[i][j] = tmp

def do(k,cnt):
    global result
    if k==0:
        for i in range(n):
            for j in range(n-1,-1,-1):
                get(i,j)
            merge(i,n-1,k)
    elif k==1:
        for j in range(n):
            for i in range(n-1,-1,-1):
                get(i,j)
            merge(n-1,j,k)
    elif k==2:
        for i in range(n):
            for j in range(n):
                get(i,j)
            merge(i,0,k)
    elif k==3:
        for j in range(n):
            for i in range(n):
                get(i,j)
            merge(0,j,k)

    # print(f'방향 : {k},cnt : {cnt}')
    for i in board:
        result = max(result,max(i))
    #     print(i)
    # print(result)
    # print('---------------')

result = 0
def f(cnt):
    global board
    if cnt >= 5:
        return
    tmp_board = [ x[:] for x in board]

    for k in range(4):
        board = [ x[:] for x in tmp_board]
        # for i in board:
        #     print(i)
        # print('to')
        do(k,cnt)
        f(cnt+1)

f(0)
print(result)