백준 삼성 코딩 기출 문제 - 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) |
