[백준] 12100 2048(easy) (python 파이썬)

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

12100번: 2048 (Easy)

---

아이디어

1. 구현이 먼저

• 문제를 보고 N최대가 20이고 이동도 5번 하므로 문제가 말한 그대로 구현하면 되겠다고 생각.
• 상, 하, 좌, 우 이동 중에 '좌'로 이동하는 것부터 구현하면 나머지도 쉽게 만들 수 있다.
• 만들수록 변수나 if문이 많아져 다시 밀고 처음부터 작성했다. 너무 많은 변수는 필요 없다. 이건 다른 구현 문제도 마찬가지라고 생각.
• '이동시킬 블록'과 '그 블록이 이동했을 때 도착하는 곳에 있는 블록'(말이 좀 이상하긴 한데) 두 개를 비교하는 것을 중심으로 코드를 짰다.

2. 백트래킹과 브루트 포스

• 상하좌우 이동 그리고 최대 5번 이동이므로 4^5(1024)개의 경우만 고려하면 된다.
• 브루트 포스 방법으로 하나하나 전부다 해보면 된다.
• 이차원 배열을 사용하니까 deepcopy를 사용해서 상, 하, 좌, 우 케이스를 나누었다.

 

---

전체 코드

import sys, copy
N = int(input())
pan = []
ans = 0

for _ in range(N):
    pan.append([int(x) for x in sys.stdin.readline().rstrip().split()])

def left(board):
    for i in range(N):
        cursor = 0
        for j in range(1, N):
            if board[i][j] != 0: # 0이 아닌 값이
                tmp = board[i][j]
                board[i][j] = 0 # 일단 비워질꺼니까 0으로 바꿈

                if board[i][cursor] == 0: # 비어있으면
                    board[i][cursor] = tmp # 옮긴다

                elif board[i][cursor] == tmp: # 같으면
                    board[i][cursor] *= 2 # 합친다
                    cursor += 1
                else: # 비어있지도 않고 다른 값일때
                    cursor += 1 # pass
                    board[i][cursor] = tmp # 바로 옆에 붙임

    return board

def right(board):
    for i in range(N):
        cursor = N - 1
        for j in range(N - 1, -1, -1):

            if board[i][j] != 0:
                tmp = board[i][j]
                board[i][j] = 0

                if board[i][cursor] == 0:
                    board[i][cursor] = tmp

                elif board[i][cursor] == tmp:
                    board[i][cursor] *= 2
                    cursor -= 1
                else:
                    cursor -= 1
                    board[i][cursor] = tmp
    return board

def up(board):
    for j in range(N):
        cursor = 0
        for i in range(N):
            if board[i][j] != 0:
                tmp = board[i][j]
                board[i][j] = 0

                if board[cursor][j] == 0:
                    board[cursor][j] = tmp

                elif board[cursor][j] == tmp:
                    board[cursor][j] *= 2
                    cursor += 1

                else:
                    cursor += 1
                    board[cursor][j] = tmp
    return board

def down(board):
    for j in range(N):
        cursor = N - 1
        for i in range(N - 1, -1, -1):
            if board[i][j] != 0:
                tmp = board[i][j]
                board[i][j] = 0

                if board[cursor][j] == 0:
                    board[cursor][j] = tmp

                elif board[cursor][j] == tmp:
                    board[cursor][j] *= 2
                    cursor -= 1

                else:
                    cursor -= 1
                    board[cursor][j] = tmp
    return board

def dfs(n, arr):
    global ans
    if n == 5:
        for i in range(N):
            for j in range(N):
                if arr[i][j] > ans:
                    ans = arr[i][j]
        return

    for i in range(4):
        copy_arr = copy.deepcopy(arr)
        if i == 0:
            dfs(n + 1, left(copy_arr))
        elif i == 1:
            dfs(n + 1, right(copy_arr))
        elif i == 2:
            dfs(n + 1, up(copy_arr))
        else:
            dfs(n + 1, down(copy_arr))

dfs(0, pan)
print(ans)

---

코드 설명

 

def left(board):
    for i in range(N):
        cursor = 0
        for j in range(1, N):
            if board[i][j] != 0: # 0이 아닌 값이
                tmp = board[i][j]
                board[i][j] = 0 # 일단 비워질꺼니까 0으로 바꿈

                if board[i][cursor] == 0: # 비어있으면
                    board[i][cursor] = tmp # 옮긴다

                elif board[i][cursor] == tmp: # 같으면
                    board[i][cursor] *= 2 # 합친다
                    cursor += 1
                else: # 비어있지도 않고 다른 값일때
                    cursor += 1 # pass
                    board[i][cursor] = tmp # 바로 옆에 붙임
    return board

먼저 블록을 이동시키는 코드.

나머지 상, 하, 우 방법도 비슷하므로 좌로 움직일 때 코드만 설명.

설명은 주석으로 하는게 편할 거 같아서 주석으로 간단하게 작성했다.

옮길 블록은 board[i][j], 옮길 블록과 바꿀 자리는 board[i][cursor]이다.

 

 

def dfs(n, arr):
    global ans
    if n == 5:
        for i in range(N):
            for j in range(N):
                if arr[i][j] > ans:
                    ans = arr[i][j]
        return

    for i in range(4):
        copy_arr = copy.deepcopy(arr)
        if i == 0:
            dfs(n + 1, left(copy_arr))
        elif i == 1:
            dfs(n + 1, right(copy_arr))
        elif i == 2:
            dfs(n + 1, up(copy_arr))
        else:
            dfs(n + 1, down(copy_arr))

n이 5가 되면(블록을 5번 이동하면) 현재 있는 이차원 배열에서 가장 큰 값을 찾아 저장하고 return 한다.

그리고 우리는 상, 하, 좌, 우 case 따로따로 확인을 해야 하므로 이차원 배열을 deepcopy로 복사해서 dfs함수에 넣어준다.