[BaekJoon] 백준 12100번 2048 (Easy)

[BaekJoon] 백준 12100번 2048 (Easy)

 

문제: www.acmicpc.net/problem/12100

 

내코드

 

- dfs와 시뮬레이션을 섞어놓은 문제

- dfs로 상하좌우 각각의 경우에 대해서 이동시키는 것을 각각 5번씩 반복했다.

- 이동 시킬때 상하우는 모두 좌로 모양을 맞춰주기 위해 list의 모양을 바꿔주었다.

- 모양을 바꿔준 후 0을 제외한 값들만 남기고 붙어있는 두 숫자가 같은 경우에 더해주었다. (ex) 2 2 4 1 1 -> 4 0 4 2 0

(이렇게 해주면 이미 한번 더해진 블럭의 경우 다시 더해지지 않는다!)

- 이후에 다시 0을 제외해준 뒤, 배열의 크기 n 에 맞게 뒤에 0을 다 붙여주었다.

- 여기까지 하고 다시 처음부터 상하좌우에 대한 이동을 반복한다.

- 5번을 다 하고 나면 최대값을 찾으면 되는 문제

 

하나에 대한 예시만 들어보자.

아래의 배열을 왼쪽으로 옮기려고 한다.

4 4 0

0 1 0

0 2 3

가 0을 제외한 값만 남기면

4 4

1

2 3

이고 여기서 두 숫자 같은 경우에 더해주면

8

1

2 3

이다.

여기서 0은 생성되지 않았으므로 뒤에 0만 붙여주자.

8 0 0

1 0 0

2 3 0

이게 왼쪽으로 옮긴 경우다.

만약 오른쪽으로 옮기고 싶다면 위의 배열을

0 4 4

0 1 0

3 2 0

으로 바꿔준 뒤 위와 같이 왼쪽으로 옮겨주자.

만약 위로 옮기고 싶다면

4 0 0

4 1 2

0 0 3

이렇게 바꿔준 뒤 위와 같이 왼쪽으로 옮겨준다.

 

import copy

n = int(input())
direction = {0: "up", 1: "down", 2: "left", 3: "right"}
answer = -1


def init():
    arr = []
    for i in range(n):
        tmp = list(map(int, input().split()))
        arr.append(tmp)
    return arr


def move(current_arr, dir_move):
    new_arr = []
    # 모든 방향에 대해 왼쪽으로 맞춰주기 위해 회전
    if dir_move == "right":
        for i in range(n):
            current_arr[i].reverse()
    elif dir_move == "up":
        for i in range(n):
            for j in range(n):
                if i > j:
                    continue
                tmp = current_arr[i][j]
                current_arr[i][j] = current_arr[j][i]
                current_arr[j][i] = tmp
    elif dir_move == "down":
        for i in range(n):
            for j in range(n):
                if i + j >= (n - 1):
                    continue
                tmp = current_arr[i][j]
                current_arr[i][j] = current_arr[n-1-j][n-1-i]
                current_arr[n-1-j][n-1-i] = tmp

    # 0을 제외한 값들만 남기
    for i in range(n):
        new_arr.append([])
        new_arr[i] = [i for i in current_arr[i] if i != 0]
    # 0번째 값이랑 1번째 값이 같다면 0번에 2배 해주고 1번은 0으로 바꿔주기
    for i in range(n):
        if len(new_arr[i]) >= 2:
            for j in range(1, len(new_arr[i])):
                if new_arr[i][j] == new_arr[i][j-1]:
                    new_arr[i][j-1] += new_arr[i][j]
                    new_arr[i][j] = 0
            new_arr[i] = [i for i in new_arr[i] if i != 0]
        for j in range(n - len(new_arr[i])):
            new_arr[i].append(0)

    return new_arr


def dfs(init_arr, num):
    global answer, direction
    # 5번 이동하면 최대값 구하기
    if num == 5:
        for i in range(n):
            answer = max(answer, max(init_arr[i]))
        return

    # 상하좌우 4개 방향에 대해 dfs 수행. 재귀로 호출하기
    for i in range(4):
        dfs(move(copy.deepcopy(init_arr), direction[i]), num + 1)


dfs(init(), 0)
print(answer)

 

참고