[Python] 백준 12100 2048(Easy)

 

 

문제

2048 게임은 4×4 크기의 보드에서 혼자 즐기는 재미있는 게임이다. 

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

 

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

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

 

 

 

난이도

골드 1

 

 

 

 

 

 

코드

import sys
import copy

def move_next(move_cnt, current_board) :
    global cnt
    global answer

    if move_cnt == 5 :
        answer = max(answer,max(map(max,current_board)))
        return
    
    for direction in ['up','down','left','right'] :
        new_board = move(copy.deepcopy(current_board), direction)
        if new_board != current_board: 
            move_next(move_cnt + 1, new_board)

    
def move(m_board,way) :
    cant_move = []
    if way == 'up' :
        for i in range(N-1) :
            for j in range(N) :
                if (i,j) in cant_move :
                    continue
                for k in range(i+1,N) :
                    if m_board[k][j] == 0 :
                        continue
                    if m_board[i][j] == 0 :
                        m_board[i][j] = m_board[k][j] 
                        m_board[k][j] = 0
                    elif m_board[i][j] == m_board[k][j] :
                        m_board[i][j] *= 2
                        m_board[k][j] = 0
                        cant_move.append((i,j))
                        break
                    else :
                        break
    elif way == 'down' :
        for i in range(N-1,0,-1) :
            for j in range(N) :
                if (i,j) in cant_move :
                    continue
                for k in range(i-1,-1,-1) :
                    if m_board[k][j] == 0:
                        continue
                    if m_board[i][j] == 0 :
                        m_board[i][j] = m_board[k][j]
                        m_board[k][j] = 0
                    elif m_board[i][j] == m_board[k][j] :
                        m_board[i][j] *= 2
                        m_board[k][j] = 0
                        cant_move.append((i,j))
                        break
                    else :
                        break
    elif way == 'left' :
        for j in range(N-1) :
            for i in range(N) :
                if (i,j) in cant_move :
                    continue
                for k in range(j+1,N) :
                    if m_board[i][k] == 0 :
                        continue
                    if m_board[i][j] == 0:
                        m_board[i][j] = m_board[i][k]
                        m_board[i][k] = 0
                    elif m_board[i][j] == m_board[i][k] :
                        m_board[i][j] *= 2
                        m_board[i][k] = 0
                        cant_move.append((i,j))
                        break
                    else :
                        break
    else :
        for j in range(N-1,0,-1) :
            for i in range(N) :
                if (i,j) in cant_move :
                    continue
                for k in range(j-1,-1,-1) :
                    if m_board[i][k] == 0 :
                        continue
                    if m_board[i][j] == 0 :
                        m_board[i][j] = m_board[i][k]
                        m_board[i][k] = 0
                    elif m_board[i][j] == m_board[i][k] :
                        m_board[i][j] *= 2
                        m_board[i][k] = 0
                        cant_move.append((i,j))
                        break
                    else :
                        break

    return m_board

N = int(sys.stdin.readline())
board = []
for _ in range(N) :
    x = list(map(int,sys.stdin.readline().split()))
    board.append(x)
answer = board[0][0]
cnt = 0

move_next(0,board)

print(answer)

 

 

 

 

 

 

풀이

백트래킹과 브루트포스 문제이다.

 

move_next(move_cnt, current_board) 함수

재귀적으로 게임판을 최대 5번까지 이동시키며 각 이동 후 얻을 수 있는 최댓값을 갱신하는 역할

• move_cnt == 5 인 경우, 이동을 종료하고 최댓값을 찾아 갱신한다.
• direction 리스트 ['up','down','left','right']를 순회하며 각 방향으로 보드를 이동하고 이동 결과가 이전 상태와 다른 경우에만 재귀 호추라여 다음 이동을 시도한다.

move(m_board, way) 함수

주어진 m_board를 way 방향으로 이동시키고 병합하는 기능

한 번 병합된 타일은 다시 병합되지 않도록 cant_move 리스트를 이용해 타일 위치를 저장한다.

 

• 위로 이동 ('up'): 아래에서 위로 순회하며, 비어 있는 공간이 있으면 타일을 위쪽으로 이동하고, 동일한 값을 만나면 병합.
• 아래로 이동 ('down'): 위에서 아래로 순회하며, 비어 있는 공간이 있으면 타일을 아래쪽으로 이동하고, 동일한 값을 만나면 병합.
• 왼쪽으로 이동 ('left'): 오른쪽에서 왼쪽으로 순회하며, 비어 있는 공간이 있으면 타일을 왼쪽으로 이동하고, 동일한 값을 만나면 병합.
• 오른쪽으로 이동 ('right'): 왼쪽에서 오른쪽으로 순회하며, 비어 있는 공간이 있으면 타일을 오른쪽으로 이동하고, 동일한 값을 만나면 병합.

 

move 함수 안에서 각 방향마다 3중 for문을 돌렸는데 나중에 board를 90도씩 회전시켜 4번 위로 이동시키는 방법도 있다는 걸 알았다.