백준 삼성 코딩 기출 문제 - 2048 (Easy) python

백준 삼성 코딩 기출 문제 - 2048 (Easy) python

출처 : BAEKJOON ONLINE JUDGE

2048 (Easy) (https://www.acmicpc.net/problem/12100)

문제 설명

2048 게임은 4×4 크기의 보드에서 같은 값을 갖는 두 블록이 충돌하면 합쳐집니다.

다음의 게임을 해보시면 이해가 갑니다ㅎㅎ 핸드폰 앱 게임으로도 많이 나와 있죠.

https://play2048.co

여기서는 NxN크기의 보드가 주어집니다. 이미 합쳐진 블록은 다른 블록과 다시 합쳐지지 않습니다. 실제 게임에서는 이동을 할 때마다 블록이 추가되지만, 이 문제에서는 추가되지는 않고 주어진 보드에서 최대 5번을 이동할 경우 가장 큰 블록 값을 구합니다.

문제 풀이

시뮬레이션을 해보는 문제입니다.

[1] 입력들을 받아들이고, queue를 생성합니다.

from collections import deque n = int(input()) board = [list(map(int, input().split())) for _ in range(n)] answer, q = 0, deque()

[2] 큰 구조로는  재귀함수를 쓰게 되고, move로 움직이고 그 이후를 재귀적으로 호출해 나가며 살펴봅니다.
- 최대 5번까지 움직였다면 멈추고 전체 배열의 최대 값을 반환합니다.
- 4방향으로 모두 움직여보고 재귀를 호출합니다.

 - 움직일 때마다 원본의 board를 기억하고 있어야 합니다.

def solve(count):     global board, answer     if count == 5: # 최대 5번까지 움직였다면         for i in range(n):             answer = max(answer, max(board[i])) # 가장 큰 값이 answer         return     b = [x[:] for x in board] # 방향을 바꾸기 전에 원래의 보드를 기억해야 한다.         for k in range(4): # 4방향으로 움직인다.         move(k) # 움직인다.         solve(count+1) # 재귀적으로 호출한다.         board = [x[:] for x in b]

[3] 우선 해당 row_index, column_index에 보드의 값을 가져옵니다. get() 보드에 0이 아닌 값이라면 큐에 넣고 0으로 처리합니다.

def get(i, j):     if board[i][j]: # 0이 아닌 값이라면         q.append(board[i][j]) # queue에 board의 값을 넣는다.         board[i][j] = 0 # 처리가 된 빈 자리는 0으로 값 업데이트

[4] move() 움직이는 방향은 상/하/좌/우가 있습니다.

- 움직이려는 방향에 따라서 column_index 또는 row_index를 바깥 for문에 둡니다. 예를 들어 위, 아래로 움직이려면 블락들이 column_index를 고정하고 row_index들이 움직입니다. 따라서 for문 바깥에는 column이 안으로는 row가 돌면서 get()을 호출에 큐에 넣습니다.
- 반대로 좌, 우로 움직이려면 블락들이 row_index가 고정이 되고, column_index들이 움직여야겠죠. 따라서 for문 바깥에는 row이 안으로는 column으로 들어와 get을 호출에 큐에 넣습니다.

 - 움직였으면 합쳐야되는 merge()를 호출합니다.

 - 위로 움직이는 경우 : 모든  블락들이 합쳐졌다면 row index는 0에 위치합니다. 위로 움직이니 차례대로 아래쪽 row index가 증가하는 방향(+1)으로 블락을 합쳐나갑니다. 

 - 아래로 움직이는 경우 : 모든  블락들이 합쳐졌다면 row index는 n-1에 위치합니다. 위로 움직이니 차례대로 아래쪽 row index가 감소하는 방향(-1)으로 블락을 합쳐나갑니다.

 - 오른쪽으로 움직이는 경우 : 모든 블락들이 합쳐졌다면 column index는 n-1에 위치 합니다. 오른쪽으로 움직이므로, 차례대로 왼쪽 column index가 감소하는 방향으로(-1)으로 블락을 합쳐집니다.

 - 왼쪽으로 움직이는 경우 : 모든 블락들이 합쳐졌다면 column index는 0에 위치 합니다. 왼쪽으로 움직이므로, 차례대로 왼쪽 column index가 감소하는 방향으로(+1)으로 블락을 합쳐집니다.

def move(k):     # board[i][j]     if k == 0: # 위로 이동, 블락들이 위로 모두 이동하면 row index는 0         for j in range(n):             for i in range(n):                 get(i, j)             merge(0, j, 1, 0) # row index 1씩 증가하면서 아래쪽 블락들을 합쳐감     elif k == 1: # 아래로 이동, 블락들이 아래로 모두 이동하면 row index는 n-1         for j in range(n):             for i in range(n-1, -1, -1):                 get(i, j)             merge(n-1, j, -1, 0) # row 인덱스 1씩 감소하면서 위쪽들을 합쳐감     elif k == 2: # 오른쪽으로 이동, column index는 0         for i in range(n):             for j in range(n):                 get(i, j)             merge(i, 0, 0, 1) # column 인덱스 증가 오른쪽으로 이동     else: # 왼쪽으로 이동, column index는 n-1         for i in range(n):             for j in range(n-1, -1, -1):                 get(i, j)             merge(i, n-1, 0, -1) # column 인덱스 감소 왼쪽으로 이동

[4] merge() 움직였으면 합쳐야겠죠.
- 큐에서 합치려는 블락들을 가져와 비교합니다.

 - 서로 값이 일치한다면 합쳐지면서 값은 2배로 증가됩니다.

 -  값이 일치하지 않거나, 0이라면 그대로 놓습니다.

def merge(i, j, di, dj): # row index, column index, y방향, x방향     while q:         x = q.popleft() # 움직이려는 블록 값을 가져온다. FIFO         if not board[i][j]: # 0이라면 그대로 놓는다.             board[i][j] = x         elif board[i][j] == x: # 값이 일치한다면             board[i][j] = x*2 # 합쳐지므로 2배로 증가             i, j = i+di, j+dj         else: # 값이 일치하지 않으면             i, j = i+di, j+dj             board[i][j] = x

전체 코드

from collections import deque n = int(input()) board = [list(map(int, input().split())) for _ in range(n)] answer, q = 0, deque() def get(i, j):     if board[i][j]: # 0이 아닌 값이라면         q.append(board[i][j]) # queue에 board의 값을 넣는다.         board[i][j] = 0 # 처리가 된 빈 자리는 0으로 값 업데이트         def merge(i, j, di, dj): # row index, column index, y방향, x방향     while q:         x = q.popleft() # 움직이려는 블록 값을 가져온다. FIFO         if not board[i][j]: # 0이라면 그대로 놓는다.             board[i][j] = x         elif board[i][j] == x: # 값이 일치한다면             board[i][j] = x*2 # 합쳐지므로 2배로 증가             i, j = i+di, j+dj         else: # 값이 일치하지 않으면             i, j = i+di, j+dj             board[i][j] = x def move(k):     # board[i][j]     if k == 0: # 위로 이동, 블락들이 위로 모두 이동하면 row index는 0         for j in range(n):             for i in range(n):                 get(i, j)             merge(0, j, 1, 0) # row index 1씩 증가하면서 아래쪽 블락들을 합쳐감     elif k == 1: # 아래로 이동, 블락들이 아래로 모두 이동하면 row index는 n-1         for j in range(n):             for i in range(n-1, -1, -1):                 get(i, j)             merge(n-1, j, -1, 0) # row 인덱스 1씩 감소하면서 위쪽들을 합쳐감     elif k == 2: # 오른쪽으로 이동, column index는 0         for i in range(n):             for j in range(n):                 get(i, j)             merge(i, 0, 0, 1) # column 인덱스 증가 오른쪽으로 이동     else: # 왼쪽으로 이동, column index는 n-1         for i in range(n):             for j in range(n-1, -1, -1):                 get(i, j)             merge(i, n-1, 0, -1) # column 인덱스 감소 왼쪽으로 이동             def solve(count):     global board, answer     if count == 5: # 최대 5번까지 움직였다면         for i in range(n):             answer = max(answer, max(board[i])) # 가장 큰 값이 answer         return     b = [x[:] for x in board] # 방향을 바꾸기 전에 원래의 보드를 기억해야 한다.         for k in range(4): # 4방향으로 움직인다.         move(k) # 움직인다.         solve(count+1) # 재귀적으로 호출한다.         board = [x[:] for x in b] solve(0) print(answer)