BOJ. 12100 2048 (Easy) (Python)

BOJ 12100. 2048 (Easy)

문제

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

12100번: 2048 (Easy)

 

🔸 접근 방법

5번밖에 안움직이므로 가능한 모든 경우를 탐색했다. 브루트 포스! 완탐!

아래로 움직이는 경우에는 밑에 있는 것들 먼저 합쳐지고, 오른쪽으로 움직이면 오른쪽에 있는 것들 먼저 합쳐지는 것을 구현하지 위해서 move Range를 만들어서 범위 값을 지정해주었다.

4 2 2 인 것을 오른쪽으로 밀어서 합치면 4 4 결과가 나와야 하는데 이번에 합쳐진 것들을 표시 안하고 그냥 같으면 합치는 방식으로 구현하면 4 4 인 경우에도 같다고 판단해서 8이 나온다. 처음에는 이것때문에 테스트 케이스에서 올바른 답이 나오지 않았었다.

moved 를 사용해서 이번에 합쳐진 것들은 한번 더 안합쳐지는 것을 체크해주고나니 문제를 풀 수 있었다.

# 12100 2048(Easy)
# 220926

import sys
input = sys.stdin.readline

# 위 오른쪽 아래 왼쪽
di = [-1, 0, 1, 0]
dj = [0, 1, 0, -1]

N = int(input())
arr = [list(map(int, input().split())) for _ in range(N)]
answer = 0

moveRange = {
    0 : [range(N), range(N)],
    1 : [range(N), range(N-1, -1, -1)],
    2 : [range(N-1, -1, -1), range(N)],
    3 : [range(N), range(N)],
    }

def move(arrMove, d):
    moved = [[0]*N for _ in range(N)]

    iRange, jRange = moveRange[d]
    for i in iRange:
        for j in jRange:
            num = arrMove[i][j]
            if num :
                ni = i + di[d]
                nj = j + dj[d]
                pi, pj = i, j

                while (0 <= ni < N) and (0<= nj < N):
                    # 빈칸인 경우 -> 이동
                    if arrMove[ni][nj] == 0:
                        arrMove[pi][pj] = 0
                        arrMove[ni][nj] = num

                        pi, pj = ni, nj
                        ni = pi + di[d]
                        nj = pj + dj[d]
                    # 같은 숫자인 경우 더하기
                    elif (arrMove[ni][nj] == num) and (moved[ni][nj] == 0):
                        arrMove[pi][pj] = 0
                        arrMove[ni][nj] = 2 * num
                        # 이번에 합친 거 표시
                        moved[ni][nj] = 1
                        break
                    # 다른 숫자인 경우 이동x
                    else:
                        break

    return arrMove

def play(arrPlay, K):
    global answer

    if K == 0:
        tmp = max([max(arrPlay[i]) for i in range(N)])
        if tmp > answer:
            answer = tmp
        return 

    # 위아래오른쪽왼쪽 이동 가능
    for d in range(4):
        # 딥카피
        arrTmp = [arrPlay[i][:] for i in range(N)]
        # 이동후 결과 배열 반환
        arrMoved = move(arrTmp, d)
        play(arrMoved, K-1)

    return 

# 최대 5번 이동 가능
play(arr, 5)

print(answer)

🔑 Key Point

🔸 먼저 합쳐지는 것에 대한 범위 설정을 해야한다.

🔸 합쳐지는 과정이 한줄씩 일어나니까 한줄씩 봐서 합쳐지는 것을 판단하거나, 합친 것들은 따로 표시해서 중복해서 합쳐지는 일이 없게 주의해야 한다.