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

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

# 2048 (Easy)

import copy
import sys
input = sys.stdin.readline
N = int(input())
arr = []
for _ in range(N):
    arr.append(list(map(int, input().split())))

dir = [[0, 1], [1, 0], [0, -1], [-1, 0]]
result = 0


def move_block(arr, n):
    set_result(arr)
    if n == 5:
        # 이동 끝
        return
    for k in range(4):
        temp = copy.deepcopy(arr)
        combine_and_move(temp, k)
        move_block(temp, n+1)


def combine_and_move(arr, k):
    is_combined = [[False] * N for _ in range(N)]
    if k == 0:
        for i in range(N):
            is_combined = [[False] * N for _ in range(N)]
            for j in range(N-1, -1, -1):
                do(i, j, arr, k, is_combined)
    elif k == 1:
        for j in range(N):
            is_combined = [[False] * N for _ in range(N)]
            for i in range(N-1, -1, -1):
                do(i, j, arr, k, is_combined)
    elif k == 2:
        for i in range(N):
            is_combined = [[False] * N for _ in range(N)]
            for j in range(N):
                do(i, j, arr, k, is_combined)
    elif k == 3:
        for j in range(N):
            is_combined = [[False] * N for _ in range(N)]
            for i in range(N):
                do(i, j, arr, k, is_combined)


def do(i, j, arr, k, is_combined):
    dx = dir[k][0]
    dy = dir[k][1]
    if arr[i][j] != 0:
        nx = i + dx
        ny = j + dy
        while 0 <= nx < N and 0 <= ny < N:
            if arr[nx][ny] == 0:
                arr[nx][ny] = arr[nx-dx][ny-dy]
                arr[nx-dx][ny-dy] = 0
            elif arr[nx][ny] == arr[nx-dx][ny-dy] and not is_combined[nx][ny] and not is_combined[nx-dx][ny-dy]:
                is_combined[nx][ny] = True
                arr[nx][ny] *= 2
                arr[nx-dx][ny-dy] = 0
            nx += dx
            ny += dy


def set_result(arr):
    global result
    max_result = 0
    for i in range(N):
        max_result = max(max_result, max(arr[i]))
    result = max(result, max_result)


move_block(arr, 0)
print(result)

 

백트랙킹, 구현(시물레이션)

1. 입력을 받고 스왑할 방향을 담은 dir리스트를 선언한다(동남서북)

2. 최대 5번 이동했을 때의 모든 경우의 수 구하기 (move_block함수)

• result를 max값으로 초기화 (set_result함수) : 모든 경우의 수마다 적용
• 방향을 정할 때마다 이동 및 합치기 (combine_and_move함수) : 한번 합쳐진 블록은 그 횟수가 실행 중에 다시 합쳐질 수 없기 때문에 is_combined리스트로 합쳐졌는지 아닌지의 상태를 보관, 횟수가 끝나면 전부 False로 초기화
• combine_and_move 함수내부의 겹치는 부분 구현 (do함수) : 방향에 알맞은 dir을 가지고 다음 값이 0이면 이동, 현재 값과 다음 값이 같고 현재 위치와 다음 위치 모두 합쳐지지 않은 상태라면 (현재 위치의 is_combined 와 다음 위치의 is_combined 값 모두 False) 합치기 수행

3. result 출력