[백준 12100] 2048 (Easy) (Python)

 

www.acmicpc.net/problem/12100

12100번: 2048 (Easy)

문제 풀이

N, board : 입력값

p: 행이나 열에서 블록이 이동하게 될 가장 끝의 위치
x: 이전 블록이 새로운 블록과 합쳐지는것을 표현 => 이전 블록을 저장하고 있는 변수

 

move_up(board) : 블록을 상단으로 이동

move_down(board) : 블록을 하단으로 이동

move_right(board) : 블록을 우측으로 이동

move_left(board) : 블록을 좌측으로 이동

solution(tmp_board, cnt) : 재귀적 방법으로 5번까지 반복해서 블록을 이동

 

 

재귀로 블록을 이동시킬 때는 반드시 board를 복사해서 사용해야 한다.(모든 경우를 해보기 위해서), 파이썬 copy 모듈의 deepcopy를 사용하거나, 직접 깊은 복사를 구현해서 사용해야 한다.

오타에 조심해야 한다! i, j 위치를 바꿔서 쓴다거나 deepcopy를 잘못하면 바로 틀렸습니다 라고 뜬다.

 

 

1. 현재까지 블록을 이동시킨 횟수가 5번이 넘으면 그때의 최대 블록 확인

 

2. deepcopy 를 사용해 블록을 복사한 후, 블록을 좌측, 우측, 상단, 하단으로 이동

 

3. 1-2 과정 반복

 

블록을 이동시키는 방법은 코드 주석으로 자세히 설명되어 있습니다.

 

 

코드

import sys
from copy import deepcopy

# 오타에 조심해야 한다. i, j 위치를 바꿔서 쓴다거나, deepcopy 를 잘못하면 바로 틀렸다고 나온다.
# p: 행이나 열에서 블록이 이동하게 될 가장 끝의 위치
# x: 블록이 합쳐지는것을 표현하기 위한 변수

def move_up(board): # 블록 위로 이동
    for i in range(N): # 열
        p = 0 # 행의 가장 상단은 0
        x = 0
        for j in range(N): # 행
            if board[j][i] == 0: continue # 0이면 continue
            if x == 0: x = board[j][i] # x가 비어있으면 더해줄 블록이 없다는 것이므로 x를 변경
            else:
                if x == board[j][i]: # 지난 블록과 같은 경우
                    board[p][i] = x * 2 # 이동할 곳에 x * 2 값을 저장
                    x = 0 # 블록을 더했으므로 x 초기화
                    p += 1 # 행에서 갈 수 있는 가장 상단 행을 채웠으므로 다음 블록이 이동하게될 위치 증가
                else: # 지난 블록과 같지 않은 경우
                    board[p][i] = x # 이동할 곳에 지난 블록인 x값을 저장
                    x = board[j][i] # 이전 블록을 새로운 블록으로 변경
                    p += 1 # 행에서 갈 수 있는 가장 상단을 채웠으므로 다음 블록이 이동하게될 위치 증가
            board[j][i] = 0 # 블록 이동했으므로 비워줌
        if x != 0: board[p][i] = x # 행의 가장 하단까지 도달 후에 이동할 블록이 남아있으면 블록 이동
    return board

def move_down(board):
    for i in range(N): # 열
        p = N - 1 # 행의 가장 하단
        x = 0
        for j in range(N - 1, -1, -1): # 행
            if board[j][i] == 0: continue # 0이면 continue
            if x == 0: x = board[j][i] # x가 비어있으면 더해줄 이전 블록이 없다는 것이므로 x를 변경
            else:
                if x == board[j][i]: # 지난 블록과 같은 경우
                    board[p][i] = x * 2 # 이동할 곳에 x * 2 값을 저장
                    x = 0 # 블록을 더했으므로 x 초기화
                    p -= 1 # 행에서 갈 수 있는 가장 하단을 채웠으므로 다음 블록이 이동하게될 위치 감소
                else: # 지난 블록과 같지 않은 경우
                    board[p][i] = x # 이동할 곳에 지난 블록인 x값을 저장
                    x = board[j][i] # 이전 블록을 새로운 블록으로 변경
                    p -= 1 # 행에서 갈 수 있는 가장 하단을 채웠으므로 다음 블록이 이동하게될 위치 감소
            board[j][i] = 0 # 블록 이동했으므로 비워줌
        if x != 0: board[p][i] = x  # 행의 가장 상단까지 도달 후에 이동할 블록이 남아있으면 블록 이동
    return board

def move_right(board):
    for i in range(N): # 행
        p = N - 1 # 열의 가장 우측
        x = 0
        for j in range(N - 1, -1, -1): # 열
            if board[i][j] == 0: continue # 비어있으면 continue
            if x == 0: x = board[i][j] # x가 비어있으면 더해줄 이전 블록이 없다는 것이므로 x를 변경
            else:
                if x == board[i][j]: # 지난 블록과 같은 경우
                    board[i][p] = x * 2 # 이동할 곳에 x * 2 값을 저장
                    x = 0 # 블록을 더했으므로 x 초기화
                    p -= 1 # 열에서 갈 수 있는 가장 우측을 채웠으므로 다음 블록이 이동하게될 위치 감소
                else:  # 지난 블록과 같지 않은 경우
                    board[i][p] = x # 이동할 곳에 지난 블록인 x값을 저장
                    x = board[i][j] # 이전 블록을 새로운 블록으로 변경
                    p -= 1 # 열에서 갈 수 있는 가장 우측을 채웠으므로 다음 블록이 이동하게될 위치 감소
            board[i][j] = 0 # 블록 이동했으므로 비워줌
        if x != 0: board[i][p] = x # 열의 좌측 끝까지 도달 후에 이동할 블록이 남아있다면 블록 이동
    return board

def move_left(board):
    for i in range(N): # 행
        p = 0 # 열의 가장 좌측
        x = 0
        for j in range(N): # 열
            if board[i][j] == 0: continue # 비어있으면 continue
            if x == 0: x = board[i][j] # x가 비어있으면 더해줄 이전 블록이 없다는 것이므로 x를 변경
            else:
                if x == board[i][j]: # 지난 블록과 같은 경우
                    board[i][p] = x * 2 # 이동할 곳에 x * 2 값을 저장
                    x = 0 # 블록을 더했으므로 x 초기화
                    p += 1 # 열에서 갈 수 있는 가장 좌측을 채웠으므로 다음 블록이 이동하게될 위치 증가
                else:
                    board[i][p] = x # 이동할 곳에 지난 블록인 x값을 저장
                    x = board[i][j] # 이전 블록을 새로운 블록으로 변경
                    p += 1 # 열에서 갈 수 있는 가장 좌측을 채웠으므로 다음 블록이 이동하게될 위치 증가
            board[i][j] = 0 # 블록 이동했으므로 비워줌
        if x != 0: board[i][p] = x # 열의 우측 끝까지 도달 후에 이동할 블록이 남아있다면 블록 이동
    return board

def solution(tmp_board, cnt):
    global ans
    if cnt == 5:  # 최대 5번만 이동 가능
        for i in range(N):
            for j in range(N):
                ans = max(ans, tmp_board[i][j]) # 현재 블록 중 최대 블록
        return

    solution(move_left(deepcopy(tmp_board)), cnt + 1) # 블록을 좌측으로 이동
    solution(move_right(deepcopy(tmp_board)), cnt + 1) # 블록을 우측으로 이동
    solution(move_up(deepcopy(tmp_board)), cnt + 1) # 블록을 상단으로 이동
    solution(move_down(deepcopy(tmp_board)), cnt + 1) # 블록을 하단으로 이동

if __name__ == '__main__':
    ans = 0
    N = int(input())
    board = [[int(x) for x in sys.stdin.readline().split()] for _ in range(N)] # 입력값
    solution(board, 0)
    print(ans)

 

결과

 

위 풀이는 'juhee-maeng' 님의 파이썬 풀이를 참고한 코드입니다.

https://juhee-maeng.tistory.com/90

 

문제풀이나 코드에서 이상한 부분 지적은 언제나 환영합니다!