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

<문제 링크>

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

12100번: 2048 (Easy)

 

<풀이 전략>

1. N이 20 이하이고 시행이 5번으로 고정되어 있어서 백트래킹을 이용한 완전탐색으로 문제를 풀 수 있다.

2. 블럭의 병합 / 이동 2가지를 상하좌우 4방향으로 구현해야되는데 나는 한 방향에 대해서만 구현하고 나머지는 배열을 회전 시켜서 적용하는 법을 이용했다. (참고: https://bluuubery.tistory.com/48?category=584396)

3. 좌 -> 우 한 방향에 대해서만 이동과 병합을 구현했는데 행 단위로 코드를 짠 덕분에 슬라이싱 등을 이용할 수 있어서 큰 어려움은 없었다.

4. 주의할 점은 블럭을 합치는 과정에서 직전/직후 원소랑만 비교를 하면 2 0 0 2 -> 0 0 0 4 같은 경우를 제대로 확인을 못하므로 이동을 먼저 하고 합쳐줘야 한다.

 

<정답 코드>

import sys, os, io, atexit

input = lambda: sys.stdin.readline().rstrip('\r\n')
stdout = io.BytesIO()
sys.stdout.write = lambda s: stdout.write(s.encode("ascii"))
atexit.register(lambda: os.write(1, stdout.getvalue()))

# 221008 12100 2048(Easy)

# 정답코드

# rotate: 배열 회전 시키는 함수 
def rotate(d):
    global arr
    # 시계방향 0도
    if d == 0:
        return

    # 시계방향 90도
    elif d == 1:
        arr = list(map(list, zip(*arr[::-1])))
        return

    # 시계방향 180도
    elif d == 2:
        arr = [[arr[N - r - 1][N - c - 1] for c in range(N)] for r in range(N)]
        return

    # 시계방향 270도    
    else:
        arr = list(map(list, zip(*arr)))[::-1]
        return


# merge: 블럭들을 합치는 함수 (행 단위)
def merge():
    
    for row in arr:
        for i in range(N - 1, 0, -1):
            # 직전 블럭과 같은 숫자일 경우
            if row[i] == row[i - 1]:
                # 해당 블럭 *2, 직전 블럭 0
                row[i] *= 2
                row[i - 1] = 0


# move: 블럭들을 한 방향으로 밀어주는 함수 (행 단위)
def move():

    for i in range(N):
        # new_row: 한 방향으로 밀린 새로운 행
        new_row = []
        # 0이 아니면 new_row에 담아준다.
        for j in range(N):
            if arr[i][j]:
                new_row.append(arr[i][j])

        # new_row앞에 0을 붙이고 원래 행이랑 바꿔준다. 
        arr[i] = [0] * (N - len(new_row)) + new_row


# 백트래킹 함수 
def back_tracking(depth):
    global ans, arr

    # 5번 다 이동했을 때 최댓값 갱신 후 반환
    if depth == 5:
        ans = max(ans, max(map(max, arr)))
        return
    
    # 상하좌우 4방향으로 블럭 이동
    for d in range(4):
        # arr_copy: 백트래킹 시 원상태 복원을 위한 복사본
        arr_copy = [arr[i][:] for i in range(N)]

        # 주어진 방향으로 배열 회전
        rotate(d)

        # 이동(합치기 위한 전처리) - 합치기 - 이동
        move()
        merge()
        move()

        # 다음 시행으로 넘어간다.
        back_tracking(depth + 1)

        # 배열 상태 복원
        arr = arr_copy


# N: 배열의 크기, arr: 배열 초기 상태
N = int(input())
arr = [list(map(int, input().split())) for _ in range(N)]

# ans: 블럭의 최댓값
ans = 0

# 백트래킹 시행
back_tracking(0)

# 정답 출력
print(ans)