[python] BOJ 백준 12100: 2048(easy)

1. 문제  

2048 게임은 4×4 크기의 보드에서 혼자 즐기는 재미있는 게임이다. 이 링크를 누르면 게임을 해볼 수 있다.

이 게임에서 한 번의 이동은 보드 위에 있는 전체 블록을 상하좌우 네 방향 중 하나로 이동시키는 것이다. 이때, 같은 값을 갖는 두 블록이 충돌하면 두 블록은 하나로 합쳐지게 된다. 한 번의 이동에서 이미 합쳐진 블록은 또 다른 블록과 다시 합쳐질 수 없다. (실제 게임에서는 이동을 한 번 할 때마다 블록이 추가되지만, 이 문제에서 블록이 추가되는 경우는 없다) 이 문제에서 다루는 2048 게임은 보드의 크기가 N×N 이다. 보드의 크기와 보드판의 블록 상태가 주어졌을 때, 최대 5번 이동해서 만들 수 있는 가장 큰 블록의 값을 구하는 프로그램을 작성하시오.

2. 입력   

첫 번째 줄에는 보드의 세로, 가로 크기를 의미하는 두 정수 N, M (3 ≤ N, M ≤ 10)이 주어진다. 다음 N개의 줄에 보드의 모양을 나타내는 길이 M의 문자열이 주어진다. 이 문자열은 '.', '#', 'O', 'R', 'B' 로 이루어져 있다. '.'은 빈 칸을 의미하고, '#'은 공이 이동할 수 없는 장애물 또는 벽을 의미하며, 'O'는 구멍의 위치를 의미한다. 'R'은 빨간 구슬의 위치, 'B'는 파란 구슬의 위치이다.

입력되는 모든 보드의 가장자리에는 모두 '#'이 있다. 구멍의 개수는 한 개 이며, 빨간 구슬과 파란 구슬은 항상 1개가 주어진다.

3. 출력   

최대 5번 이동시켜서 얻을 수 있는 가장 큰 블록을 출력한다.

4. 해결방법   

삼성에서 자주 출제하는 시뮬레이션 문제이다. 알고리즘은 간단하지만 숫자를 움직이는 코드가 까다롭다. 일단 위, 아래, 오른쪽, 왼쪽으로 움직이는 함수를 만들어줘야한다. 이때 주의할 점은, 끝단에 있는 숫자를 항상 염두해두고, 숫자가 만약에 같다면 2배를 해주고, 아니라면 움직인 위치에 그 숫자가 그대로 있게끔 해주어야한다. 움직이는 함수를 각각 만들어주고 나면, 재귀적으로 현재 보드에서 상,하,좌,우로 움직여주면된다. 이때 copy 라이브러리의 deepcopy 모듈을 사용하여 solution 함수에 넣어주어야 움직이고 난 후의 보드 상태를 다음 상태로 반환할 수 있다.  

1) 상하좌우로 움직여줄 4개의 move함수를 각각 만들어준다. 

2) 재귀적으로 상하좌우로 보드값을 움직인다. 움직인 횟수가 5번이 되면 최대값을 조사하여 반환한다. 

 

5) 구현코드

from copy import deepcopy

#위로 움직이기
def move_up(board): 
	#보드값을 하나씩 조사 
    for i in range(N): 
        p = 0 #행의 가장 상단 
        x = 0 #현재 값
        for j in range(N): 
            if board[j][i] == 0: #0이면 통과 
              continue 
            if x == 0: #현재값이 0이면 
              x = board[j][i] #현재값 저장 
            else:
                if x == board[j][i]: #현재값과 보드값이 같으면  
                    board[p][i] = x * 2  #보드값 2배증가
                    x = 0 #현재값 초기화
                    p += 1 #행 증가 
                else: 
                    board[p][i] = 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 
            if x == 0: x = board[j][i] 
            else:
                if x == board[j][i]: 
                    board[p][i] = x * 2 
                    x = 0 
                    p -= 1 
                else: 
                    board[p][i] = 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 
            if x == 0: 
              x = board[i][j] 
            else:
                if x == board[i][j]:
                    board[i][p] = x * 2 
                    x = 0
                    p -= 1 
                else: 
                    board[i][p] = 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 
            if x == 0: x = board[i][j] 
            else:
                if x == board[i][j]: 
                    board[i][p] = x * 2 
                    x = 0 
                    p += 1 
                else:
                    board[i][p] = 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
        
	#움직인횟수가 5번이 될때까지 재귀
    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) 


ans = 0
n = int(input())
board = [list(input().split()) for _ in range(n)]
solution(board, 0)
print(ans)

 

⭐️난이도:  골드2⭐️ 

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

12100번: 2048 (Easy)

참고한 코드: https://baby-ohgu.tistory.com/4

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