[백준] 12100 2048 (Easy) (파이썬)

골드 Ⅱ

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

12100번: 2048 (Easy)

 

📄 문제

• 2048 게임은 N×N 크기의 보드에서 혼자 즐기는 재미있는 게임이다.
• 이 게임에서 한 번의 이동은 보드 위에 있는 전체 블록을 상하좌우 네 방향 중 하나로 이동시키는 것이다.
• 이때, 같은 값을 갖는 두 블록이 충돌하면 두 블록은 하나로 합쳐지게 된다.
• 한 번의 이동에서 이미 합쳐진 블록은 또 다른 블록과 다시 합쳐질 수 없다.
• 똑같은 수가 세 개가 있는 경우에는 이동하려고 하는 쪽의 칸이 먼저 합쳐진다.
• 예를 들어, 위로 이동시키는 경우에는 위쪽에 있는 블록이 먼저 합쳐지게 된다.

 

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

 

---

💡 아이디어

• 시간제한이 1초이고 보드의 크기가 N (1 ≤ N ≤ 20), 4방향으로 최대 5번 이동가능하다.
• 시간복잡도는 4방향으로 최대 5번이동하므로 4^5와  최대 보드 크기 20*20 을 곱한 정도이다.
• 4^5 * 20*20  정도 이므로 완전 탐색으로 문제를 해결하면 된다.
• 이문제는 보드 위에 있는 전체 블록을 상하좌우 네 방향 중 하나로 이동시키는 것이 중요하다.
• 따라서, 보드 전체를 상하좌우 4방향으로 움직이는 함수가 필요하다.
• 블록을 이동시킬 때 나올 수 있는 3가지 경우를 고려하여 함수를 생성하면 된다. 
  1. 같은 수를 만나 합쳐지는 경우
  2. 같은 수를 만났지만 이전에 이미 합쳐진 수이므로  합쳐지지 않고 이어 붙는 경우
  3. 다른 수를 만나 이어 붙는 경우
• 보드 전체를 동서남북 방향으로 5번 이동시키는 함수가 필요하다. (재귀 함수)
• 각 움직임에 따른 보드의 모양을 저장하고 다음 움직임을 시행해야 한다. (깊은 복사)
• 5번의 이동을 마친 보드에서 최댓값을 찾아 전체 경우의 최댓값을 갱신한다.
• 전체 경우의 최대 값을 출력한다.

 

1. 보드 전체를 상하좌우 4방향으로 움직이는 함수 (구현)

• 0으로 이루어진 새로운 보드를 생성한다.
• 움직이고자 하는 방향의 끝 지점부터 순서대로 보드를 탐색한다.
  • 동쪽으로 밀어주면 열 인덱스 (n-1) → 0의 방향으로 탐색
  • 서쪽으로 밀어주면 열 인덱스 0 → (n-1)의 방향으로 탐색
  • 북쪽으로 밀어주면 행 인덱스 0 → (n-1)의 방향으로 탐색
  • 남쪽으로 밀어주면 행 인덱스 (n-1) → 0의 방향으로 탐색 

• 숫자가 적힌 블록이 나오면 새로운 보드에 빈 공간 없이 순차적으로 숫자를 저장한다.
• 이동 방향에 따라 새로운 보드의 시작 인덱스가 달라진다.
  • 동쪽으로 밀어주면 열 인덱스 (n-1)부터 저장
  • 서쪽으로 밀어주면 열 인덱스 0부터 저장
  • 북쪽으로 밀어주면 행 인덱스 0부터 저장
  • 남쪽으로 밀어주면 행 인덱스 (n-1)부터 저장

• 이동시킬 때 이전에 저장된 블록의 수와 같은 값을 갖는 블록이 나오면 이전 블록이 합쳐진 블록인지 여부를 확인한다.
• 이전 블록이 합쳐진 블록이 아니면 새 보드에 저장된 이전 블록의 위치 값을 두 블록의 숫자를 합친 값으로 변경한다.
  • 새 보드의 저장 위치 인덱스(idx)는 이미 다음 위치를 향하고 있기 때문에 유지한다.
  • 합쳐진 수인 지 여부(pre_join)는 True로 변경한다.

• 이전 블록이 이미 합쳐진 블록이라면 옆에 이어 붙인다.
  • 현재 위치 인덱스(idx)는 다음 위치를 향해야 하기 때문에 + 1을 해준다.
  • 합쳐진 수인 지 여부(pre_join)는 False로 변경한다.

• 이전 블록과 다른 수가 나오면 옆에 이어 붙인다.
  • 현재 위치 인덱스(idx)는 다음 위치를 향해야 하기 때문에 + 1을 해준다.
  • 합쳐진 수인 지 여부(pre_join)는 False로 변경한다.

• 탐색이 종료되면 변경된 새로운 보드를 return 한다.

 

2. 보드 전체를 동서남북 방향으로 5번 이동시키는 함수 (재귀 - 브루트포스)

• 5번을 시행해야 하기 때문에 재귀함수로 구현한다.
• 상하좌우(동서남북) 4방향으로 전체 보드를 이동시키며 5번의 탐색을 수행한다.
• 하나의 보드를 상하좌우로 이동시킬때  깊은 복사(Deep Copy)를 사용하여 매번 변경된 보드를 복사해줘야 한다.
  • 현재 보드 상태에서 상, 하, 좌, 우로 각각 이동하므로 서로 연결되어 변경된 모양으로 다른 연산에 쓰이지 않게 해야한다.
  • 즉, 북쪽으로 이동된 모양이 다시 남쪽이나 동쪽이나 서쪽으로 이동하지 않게 해야한다.
  • 따라서, 모양은 같지만 주소 값이 다른 새로운 보드를 사용해야 한다.

• cnt를 0부터 시작하여 재귀 함수가 시행될 때마다 cnt+1을 해준다.
• cnt = 5가 되면 재귀를 종료하고 결과 보드에서 최댓값을 찾는다.

 

📝 문제 풀이 (Code)

from copy import deepcopy

# 서쪽
def west_move(move_board):
    new_board = [[0]*n for _ in range(n)]

    for wi in range(n):
        idx = 0
        pre_join = True
        for wj in range(n):
            # 0이 아니면
            if move_board[wi][wj]:
                # 바로 이전에 안 합쳐졌고, 이전 값과 같은 값을 가지면
                if not pre_join and new_board[wi][idx-1] == move_board[wi][wj]:
                    new_board[wi][idx-1] += move_board[wi][wj]
                    pre_join = True
                    continue

                # 이전에 안합쳐 쳤거나 이전값과 다르면 신경안쓰고 추가
                new_board[wi][idx] = move_board[wi][wj]
                idx += 1
                pre_join = False

    return new_board


# 동쪽
def east_move(move_board):
    new_board = [[0] * n for _ in range(n)]

    for ei in range(n):
        idx = n-1
        pre_join = True
        for ej in range(n-1,-1,-1):
            # 0이 아니면
            if move_board[ei][ej]:

                if not pre_join and new_board[ei][idx+1] == move_board[ei][ej]:
                        new_board[ei][idx+1] += move_board[ei][ej]
                        pre_join = True
                        continue

                new_board[ei][idx] = move_board[ei][ej]
                idx -= 1
                pre_join = False

    return new_board


# 북쪽
def north_move(move_board):
    new_board = [[0] * n for _ in range(n)]

    for ni in range(n):
        idx = 0
        pre_join = True
        for nj in range(n):
            # 0이 아니면
            if move_board[nj][ni]:

                if not pre_join and new_board[idx-1][ni] == move_board[nj][ni]:
                    new_board[idx-1][ni] += move_board[nj][ni]
                    pre_join = True
                    continue

                new_board[idx][ni] = move_board[nj][ni]
                idx += 1
                pre_join = False

    return new_board


# 남쪽
def south_move(move_board):
    new_board = [[0] * n for _ in range(n)]

    for si in range(n):
        idx = n-1
        pre_join = True
        for sj in range(n-1,-1,-1):
            # 0이 아니면
            if move_board[sj][si]:

                if not pre_join and new_board[idx+1][si] == move_board[sj][si]:
                    new_board[idx+1][si] += move_board[sj][si]
                    pre_join = True
                    continue

                new_board[idx][si] = move_board[sj][si]
                idx -= 1
                pre_join = False

    return new_board


def bruteforce(cnt, game_board):
    global ans

    # 최댓값 찾기
    if cnt == 5:
        for i in range(n):
            ans = max(ans, max(game_board[i]))
        return

    bruteforce(cnt + 1, east_move(deepcopy(game_board)))
    bruteforce(cnt + 1, west_move(deepcopy(game_board)))
    bruteforce(cnt + 1, south_move(deepcopy(game_board)))
    bruteforce(cnt + 1, north_move(deepcopy(game_board)))


# 완전 탐색
n = int(input())
board = [list(map(int,input().split())) for _ in range(n)]
ans = 0
bruteforce(0, board)
print(ans)