[백준(BOJ)] #12100- 2048 (Easy) (파이썬, Python3)

문제

 

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

12100번: 2048 (Easy)

---

문제 풀이

문제 설명 그대로 2048 게임을 구현하는 문제입니다. 

 

https://play2048.co/

2048

문제에도 나와있지만 위 링크를 통해 2048 게임이 생소하신 분들은 직접 플레이해볼 수 있습니다!

 

블록 이동

블록 전체는 상하좌우로 이동할 수 있기 때문에 각 방향으로 움직이는 함수 네 개를 만들었습니다. 백트래킹을 위해 보드 원본을 이동시키지 않았고, 새 보드를 만들어 그 보드에 이동된 블록의 정보를 저장하고 반환하는 방식으로 함수를 구현했습니다. 

 

다음은 블록 전체를 위로 이동했을 때의 예시입니다.

 

1) 블록을 위로 이동시키기 위해 이동하는 방향인 위에서부터 탐색을 합니다. 먼저 제일 위에 있는 숫자 4를 기준으로 잡습니다. 새 보드는 원래의 보드와 같은 방향으로 하되 인덱스는 따로 움직입니다. 새 보드도 마찬가지로 맨 위에서부터 값을 저장하기 때문에 처음 행의 인덱스는 0입니다.

 

2) 다음으로 온 숫자는 4로 기준 숫자 4와 같기 때문에 8을 새 보드의 지정된 인덱스에 저장하고 새 보드의 인덱스를 1 증가시킵니다.

 

3) 다음으로 온 숫자 8을 기준으로 잡습니다.

 

4) 다음으로 온 숫자는 4로 기준 숫자 8과 다르기 때문에 기준 숫자 8을 새 보드의 지정된 인덱스에 저장하고 새 보드의 인덱스를 1 증가시킵니다.

 

5) 한 열 탐색을 다 끝내고 남은 숫자는 4이기 때문에 4는 그대로 새 보드의 지정된 인덱스에 저장을 합니다.

 

6) 같은 방법으로 나머지 열에도 적용하면 오른쪽과 같이 모든 블록이 이동하게 됩니다.

 

이런 방법으로 모든 방향으로의 이동에 적용시켜주면 됩니다.

 

블록 이동시 방향에 따른 반복문 플로우는 위와 같습니다.

 

경우의 수

블록 이동 함수는 다 구현했고, 이제 이동에 따른 경우의 수를 구해 어떤 경우에서 보드의 블록 값이 최대가 되는 지를 구하면 됩니다. 저는 DFS로 구현을 했고, 위에서도 언급했듯이 보드 이동을 할 때는 새 보드를 만들어 반환하는 형식으로 구현을 했기 때문에 백트래킹을 적용할 수 있었습니다.

 

2022.07.12 - [PS/알고리즘 이론] - [파이썬으로 배우는 알고리즘] DFS(깊이 우선 탐색)

[파이썬으로 배우는 알고리즘] DFS(깊이 우선 탐색)

 

---

구현

코드

import sys
input = sys.stdin.readline

def move_up(t_board):    
    t_list = [[0] * n for _ in range(n)]                 
    for i in range(n):
        index = 0
        p = -1
        flag = False
        
        for j in range(n):
            # 해당 자리에 블록이 존재하면
            if t_board[j][i] != 0:
                # 아직 기준을 정하지 않았으면 기준으로 설정
                if not flag:
                    p = t_board[j][i]
                    flag = True
                else:
                    # 기준으로 잡은 값과 같다면
                    if p == t_board[j][i]:
                        # 더한 값을 새 보드 인덱스에 저장
                        t_list[index][i] = p * 2
                        p = -1
                        flag = False
                    else:
                        t_list[index][i] = p
                        p = t_board[j][i]
                    index += 1
        # 탐색을 마친 뒤 값이 남아있다면
        if p != -1:
            # 새 보드 인덱스에 저장
            t_list[index][i] = p
                        
    return t_list
            
def move_right(t_board):    
    t_list = [[0] * n for _ in range(n)]                 
    for i in range(n):
        index = n-1
        p = -1
        flag = False
        
        for j in range(n-1, -1, -1):
            # 해당 자리에 블록이 존재하면
            if t_board[i][j] != 0:
                # 아직 기준을 정하지 않았으면 기준으로 설정
                if not flag:
                    p = t_board[i][j]
                    flag = True
                else:
                    # 기준으로 잡은 값과 같다면
                    if p == t_board[i][j]:
                        # 더한 값을 새 보드 인덱스에 저장
                        t_list[i][index] = p * 2
                        p = -1
                        flag = False
                    else:
                        t_list[i][index] = p
                        p = t_board[i][j]
                    index -= 1
        # 탐색을 마친 뒤 값이 남아있다면
        if p != -1:
            # 새 보드 인덱스에 저장
            t_list[i][index] = p
                        
    return t_list

def move_down(t_board):                 
    t_list = [[0] * n for _ in range(n)]                 
    for i in range(n):
        index = n-1
        p = -1
        flag = False
        
        for j in range(n-1, -1, -1):
            # 해당 자리에 블록이 존재하면
            if t_board[j][i] != 0:
                # 아직 기준을 정하지 않았으면 기준으로 설정
                if not flag:
                    p = t_board[j][i]
                    flag = True
                else:
                    # 기준으로 잡은 값과 같다면
                    if p == t_board[j][i]:
                        # 더한 값을 새 보드 인덱스에 저장
                        t_list[index][i] = p * 2
                        p = -1
                        flag = False
                    else:
                        t_list[index][i] = p
                        p = t_board[j][i]
                    index -= 1
        # 탐색을 마친 뒤 값이 남아있다면
        if p != -1:
            # 새 보드 인덱스에 저장
            t_list[index][i] = p
                        
    return t_list

def move_left(t_board):
    t_list = [[0] * n for _ in range(n)]                 
    for i in range(n):
        index = 0
        p = -1
        flag = False
        
        for j in range(n):
            # 해당 자리에 블록이 존재하면
            if t_board[i][j] != 0:
                # 아직 기준을 정하지 않았으면 기준으로 설정
                if not flag:
                    p = t_board[i][j]
                    flag = True
                else:
                    # 기준으로 잡은 값과 같다면
                    if p == t_board[i][j]:
                        # 더한 값을 새 보드 인덱스에 저장
                        t_list[i][index] = p * 2
                        p = -1
                        flag = False
                    else:
                        t_list[i][index] = p
                        p = t_board[i][j]
                    index += 1
        # 탐색을 마친 뒤 값이 남아있다면
        if p != -1:
            # 새 보드 인덱스에 저장
            t_list[i][index] = p
                        
    return t_list

def dfs(t_board, num):
    global max_block
    # 다섯번을 모두 수행했으면
    if num == 5:
        # 최대값 도출
        for i in range(n):
            for j in range(n):
                max_block = max(max_block, t_board[i][j])
        return
    else:
        t = move_up(t_board)
        dfs(t, num + 1)
        t = move_right(t_board)
        dfs(t, num + 1)
        t = move_left(t_board)
        dfs(t, num + 1)
        t = move_down(t_board)
        dfs(t, num + 1)

if __name__ == "__main__":
    n = int(input())
    board = [list(map(int, input().split())) for _ in range(n)]
    max_block = 0
    
    dfs(board, 0)
    print(max_block)

결과