[파이썬 | BOJ | 12100] 2048

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

12100번: 2048 (Easy)

문제

2048 게임은 4×4 크기의 보드에서 혼자 즐기는 재미있는 게임이다. 이 링크를 누르면 게임을 해볼 수 있다.

이 게임에서 한 번의 이동은 보드 위에 있는 전체 블록을 상하좌우 네 방향 중 하나로 이동시키는 것이다. 이때, 같은 값을 갖는 두 블록이 충돌하면 두 블록은 하나로 합쳐지게 된다. 한 번의 이동에서 이미 합쳐진 블록은 또 다른 블록과 다시 합쳐질 수 없다. (실제 게임에서는 이동을 한 번 할 때마다 블록이 추가되지만, 이 문제에서 블록이 추가되는 경우는 없다)

 

<그림 1>의 경우에서 위로 블록을 이동시키면 <그림 2>의 상태가 된다. 여기서, 왼쪽으로 블록을 이동시키면 <그림 3>의 상태가 된다.

 

<그림 4>의 상태에서 블록을 오른쪽으로 이동시키면 <그림 5>가 되고, 여기서 다시 위로 블록을 이동시키면 <그림 6>이 된다. 여기서 오른쪽으로 블록을 이동시켜 <그림 7>을 만들 수 있다.

 

<그림 8>의 상태에서 왼쪽으로 블록을 옮기면 어떻게 될까? 2가 충돌하기 때문에, 4로 합쳐지게 되고 <그림 9>의 상태가 된다.

 

<그림 10>에서 위로 블록을 이동시키면 <그림 11>의 상태가 된다. 

<그림 12>의 경우에 위로 블록을 이동시키면 <그림 13>의 상태가 되는데, 그 이유는 한 번의 이동에서 이미 합쳐진 블록은 또 합쳐질 수 없기 때문이다.

 

마지막으로, 똑같은 수가 세 개가 있는 경우에는 이동하려고 하는 쪽의 칸이 먼저 합쳐진다. 예를 들어, 위로 이동시키는 경우에는 위쪽에 있는 블록이 먼저 합쳐지게 된다. <그림 14>의 경우에 위로 이동하면 <그림 15>를 만든다.

이 문제에서 다루는 2048 게임은 보드의 크기가 N×N 이다. 보드의 크기와 보드판의 블록 상태가 주어졌을 때, 최대 5번 이동해서 만들 수 있는 가장 큰 블록의 값을 구하는 프로그램을 작성하시오.

입력

첫째 줄에 보드의 크기 N (1 ≤ N ≤ 20)이 주어진다. 둘째 줄부터 N개의 줄에는 게임판의 초기 상태가 주어진다. 0은 빈 칸을 나타내며, 이외의 값은 모두 블록을 나타낸다. 블록에 쓰여 있는 수는 2보다 크거나 같고, 1024보다 작거나 같은 2의 제곱꼴이다. 블록은 적어도 하나 주어진다.

출력

최대 5번 이동시켜서 얻을 수 있는 가장 큰 블록을 출력한다.

풀이

알고리즘 분류 : 시뮬레이션, 구현

 

일단 문제에서 정의된 것 처럼, 상 하 좌 우 이동할 때 board의 값을 바꿔주어야 한다.

pop 및 append를 index를 이용해서 수행하기 위해서, row와 column의 list로 나누어서 관리한다.

 

위쪽으로 숫자들을 옮기는 경우로 생각해보면, 숫자가 0이 아니면 숫자를 맨 위쪽으로 옮겨야 하므로, 위쪽 기준으로는 column list의 앞쪽으로 옮겨야 한다. 따라서 column 기준으로 위쪽에서 아래로 탐색하면서, 숫자가 0이면 pop해서, 맨 뒤에다가 append해준다.

 

반대로 아래쪽으로 숫자들을 옮기는 경우는 column 기준으로 아래에서 위쪽으로 탐색하면서, 숫자가 0이면 pop해서 맨 앞에다가 append해준다(insert(0, 넣을값)으로 구현)

 

좌, 우는 마찬가지 알고리즘을 row 기준으로 구성해준다.

 

위의 알고리즘을 move함수로 정의하면, 일단 숫자들을 한쪽으로 몰았으므로, 같은 숫자 2개가 만나면 합쳐줘야한다.

 

위쪽으로 옮기는 경우, column기준으로 위쪽에서 아래로 탐색하면서, 서로 인접한 숫자가 같으면, 앞쪽은 2배, 뒤쪽은 0으로 만들어주는 처리를 해주고, 한번더 move를 수행해 주어야한다. 왜냐하면 어떤 column list가 [2 2 2 0] 이었다면 [4 0 2 0]이 되었으므로 다시 move를 해서 [4 2 0 0]으로 변환해주어야 한다.

 

따라서 move함수에 첫번째 호출인지 두번째 호출인지 구분하는 인자를 전달해서 첫번째 move 호출일때만 check하도록 구현했다.

 

위의 move 함수를 구현했으므로 이제 총 상하좌우 4가지 경우의 수를 5번 수행하면 되므로 총 1024가지의 경우의 수가 나온다.

 

재귀적으로 구성해도 되는데, 처음 프로그램을 구성할 때 전역변수 row, column을 구성해서 변환시키는 알고리즘을 구성했기때문에 그냥 1024개의 케이스를 반복하는 방법으로 답을 구했다.

 

 

# [파이썬 | BOJ | 12100] 2048(easy)
 
import sys
from copy import deepcopy
read = sys.stdin.readline
 
bins = [2**i for i in range(20)]
 
NOTATION = '0123456789ABCDEF'
 
def numeral_system(number, base):
    q, r = divmod(number, base)
    n = NOTATION[r]
    return numeral_system(q, base) + n if q else n
 
def maxval():
    ret = -1
    for r in row:
        if ret < max(r):
            ret = max(r)
    return ret
 
def myPrint():
    print('------row-------')
    for r in row:
        print(r)
    print('------column-------')
    for i in range(N):
        for j in range(N):
            print(column[j][i], end=' ')
        print()
 
def sync(op):
    #column to row
    if op == 1:
        for i in range(N):
            for j in range(N):
                row[i][j] = column[j][i]
    
    #row to column
    else:
        for i in range(N):
            for j in range(N):
                column[j][i] = row[i][j]
 
def check(direction):
    if direction == 0:      #상
        for i in range(N):
            for j in range(N-1):
                if column[i][j] == column[i][j+1] and column[i][j] != 0:
                    column[i][j] *= 2
                    column[i][j+1] = 0
  
    elif direction == 1:    #하
        for i in range(N):
            for j in reversed(range(1, N)):
                if column[i][j] == column[i][j-1] and column[i][j] != 0:
                    column[i][j] *= 2
                    column[i][j-1] = 0
 
    elif direction == 2:    #좌
        for i in range(N):
            for j in range(N-1):
                if row[i][j] == row[i][j+1] and row[i][j] != 0:
                    row[i][j] *= 2
                    row[i][j+1] = 0
 
    elif direction == 3:    #우
        for i in range(N):
            for j in reversed(range(1, N)):
                if row[i][j] == row[i][j-1] and row[i][j] != 0:
                    row[i][j] *= 2
                    row[i][j-1] = 0
 
def move(direction, doCheck):
    if direction == 0:      #상
        for i in range(N):
            for j in range(N):
                cnt = 0
                while (not column[i][j] in bins) and (cnt < N-j):
                    column[i].append(column[i].pop(j))
                    cnt += 1
        if doCheck:
            check(direction)
            move(direction, False)
        else:
            sync(1)
 
    elif direction == 1:    #하
        for i in range(N):
            for j in reversed(range(N)):
                cnt = 0
                while (not column[i][j] in bins) and (cnt < j):
                    column[i].insert(0, column[i].pop(j))
                    cnt += 1
        if doCheck:
            check(direction)
            move(direction, False)
        else:
            sync(1)
 
    elif direction == 2:    #좌
        for i in range(N):
            for j in range(N):
                cnt = 0
                while (not row[i][j] in bins) and (cnt < N-j):
                    row[i].append(row[i].pop(j))
                    cnt += 1
        if doCheck:
            check(direction)
            move(direction, False)
        else:
            sync(2)
 
    elif direction == 3:    #우
        for i in range(N):
            for j in reversed(range(N)):
                cnt = 0
                while (not row[i][j] in bins) and (cnt < j):
                    row[i].insert(0, row[i].pop(j))
                    cnt += 1
        if doCheck:
            check(direction)
            move(direction, False)
        else:
            sync(2)
        
N = int(read())
baseRow = []
baseColumn = []
for _ in range(N):
    baseRow.append(list(map(int, read().split())))
for i in range(N):
    temp = []
    for j in range(N):
        temp.append(baseRow[j][i])
    baseColumn.append(temp)
 
ans = -1
for i in range(1024):
    row = deepcopy(baseRow)
    column = deepcopy(baseColumn)
 
    num = (numeral_system(i, 4))
    if len(num) < 5:
        num = '0' * (5-len(num)) + num
    #print(num)
 
    for n in num:
        move(int(n), True)
    temp = maxval()
    #print(temp)
    if ans < temp:
        ans = temp
 
print(ans)