백준 12100번: 2048 (Easy) (Python)

접근

DFS 알고리즘을 이용한 방법으로 풀이를 진행하였고,

보드를 각 위, 아래, 왼쪽, 오른쪽으로 이동시키는 move_up, move_down, move_left, move_right 함수와, 문제를 푸는 solve 재귀 함수를 이용하여 문제를 해결하였다.

solve 함수에서는 보드를 각각 4방향으로 이동시키며 depth를 1씩 증가시키며 깊이 들어가게 되고, depth가 5가 되는 순간 보드에서 가장 큰 값을 저장하고 이전 단계로 돌아가게 된다.

코드

from copy import deepcopy

N = int(input())
matrix = []
for i in range(N):
    matrix.append(list(map(int, input().split())))
ans = []


def move_left(matrix):
    for r in range(N):
        cnt = 0
        now = 0
        for c in range(N):
            if matrix[r][c] == 0:
                continue
            if now == 0:
                now = matrix[r][c]
            else:
                if now == matrix[r][c]:
                    matrix[r][cnt] = 2 * now
                    now = 0
                    cnt += 1
                else:
                    matrix[r][cnt] = now
                    now = matrix[r][c]
                    cnt += 1
            matrix[r][c] = 0
        if now != 0:
            matrix[r][cnt] = now
    return matrix


def move_right(matrix):
    for r in range(N):
        cnt = N - 1
        now = 0
        for c in range(N - 1, -1, -1):
            if matrix[r][c] == 0:
                continue
            if now == 0:
                now = matrix[r][c]
            else:
                if now == matrix[r][c]:
                    matrix[r][cnt] = 2 * now
                    now = 0
                    cnt -= 1
                else:
                    matrix[r][cnt] = now
                    now = matrix[r][c]
                    cnt -= 1
            matrix[r][c] = 0
        if now != 0:
            matrix[r][cnt] = now
    return matrix


def move_up(matrix):
    for c in range(N):
        cnt = 0
        now = 0
        for r in range(N):
            if matrix[r][c] == 0:
                continue
            if now == 0:
                now = matrix[r][c]
            else:
                if now == matrix[r][c]:
                    matrix[cnt][c] = 2 * now
                    now = 0
                    cnt += 1
                else:
                    matrix[cnt][c] = now
                    now = matrix[r][c]
                    cnt += 1
            matrix[r][c] = 0
        if now != 0:
            matrix[cnt][c] = now
    return matrix


def move_down(matrix):
    for c in range(N):
        cnt = N - 1
        now = 0
        for r in range(N - 1, -1, -1):
            if matrix[r][c] == 0:
                continue
            if now == 0:
                now = matrix[r][c]
            else:
                if now == matrix[r][c]:
                    matrix[cnt][c] = 2 * now
                    now = 0
                    cnt -= 1
                else:
                    matrix[cnt][c] = now
                    now = matrix[r][c]
                    cnt -= 1
            matrix[r][c] = 0
        if now != 0:
            matrix[cnt][c] = now
    return matrix


def solve(matrix, depth):
    if depth == 5:
        max_val = 0
        for i in range(N):
            max_val = max(max_val, max(matrix[i]))
        ans.append(max_val)
        return

    solve(move_up(deepcopy(matrix)), depth + 1)
    solve(move_down(deepcopy(matrix)), depth + 1)
    solve(move_left(deepcopy(matrix)), depth + 1)
    solve(move_right(deepcopy(matrix)), depth + 1)


solve(matrix, 0)
print(max(ans))

더 생각해 볼 것?

...

코드나 내용 관련 조언, 부족한 점 및 질문 언제든 환영합니다!