📄 문제
백준
난이도 : Gold 2
문제 제목 : 2048 (Easy)
✏️ 풀이 1
import sys
from copy import deepcopy
input = sys.stdin.readline
n = int(input())
board = []
for _ in range(n):
board.append(list(map(int, input().split())))
def left_upd(board):
for i in range(n):
cursor = 0
for j in range(1, n):
if board[i][j]:
tmp = board[i][j]
board[i][j] = 0
if not board[i][cursor]:
board[i][cursor] = tmp
elif board[i][cursor] == tmp:
board[i][cursor] *= 2
cursor += 1
else:
cursor += 1
board[i][cursor] = tmp
return board
def right_upd(board):
for i in range(n):
cursor = n - 1
for j in range(n - 1, -1, -1):
if board[i][j] != 0:
tmp = board[i][j]
board[i][j] = 0
if board[i][cursor] == 0:
board[i][cursor] = tmp
elif board[i][cursor] == tmp:
board[i][cursor] *= 2
cursor -= 1
else:
cursor -= 1
board[i][cursor] = tmp
return board
def up_upd(board):
for j in range(n):
cursor = 0
for i in range(n):
if board[i][j] != 0:
tmp = board[i][j]
board[i][j] = 0
if board[cursor][j] == 0:
board[cursor][j] = tmp
elif board[cursor][j] == tmp:
board[cursor][j] *= 2
cursor += 1
else:
cursor += 1
board[cursor][j] = tmp
return board
def down_upd(board):
for j in range(n):
cursor = n - 1
for i in range(n - 1, -1, -1):
if board[i][j] != 0:
tmp = board[i][j]
board[i][j] = 0
if board[cursor][j] == 0:
board[cursor][j] = tmp
elif board[cursor][j] == tmp:
board[cursor][j] *= 2
cursor -= 1
else:
cursor -= 1
board[cursor][j] = tmp
return board
result = 0
def dfs(k, arr):
global result
if k == 5:
for i in range(n):
for j in range(n):
if arr[i][j] > result:
result = arr[i][j]
return
for i in range(4):
copy_arr = deepcopy(arr)
if i == 0:
dfs(k + 1, left_upd(copy_arr))
elif i == 1:
dfs(k + 1, right_upd(copy_arr))
elif i == 2:
dfs(k + 1, up_upd(copy_arr))
else:
dfs(k + 1, down_upd(copy_arr))
dfs(0, board)
print(result)✅ 풀이 한줄 설명:
1. 게임보드를 상하좌우 중 한 쪽으로 민 결과를 업데이트하기
2. 5번 각각 미는 방향(조합)을 정하기
✅ 풀이 자세한 설명:
우선 2번의 경우 백트래킹(DFS)로 정할 수 있다.
그리고 1번의 경우, 한 쪽으로 밀었을 때 나올 수 있는 모든 경우에 대해 잘 정리하여 구현해야 한다. 상하좌우 중 한 경우에 대한 게임보드 업데이트 함수만 구현한다면, 나머지 세 경우도 같은 과정을 거치기 때문에 쉽게 해결할 수 있다.
🍎 1. 게임보드를 상하좌우 중 한 쪽으로 민 결과를 업데이트하기
게임보드를 왼쪽으로 밀 때를 기준으로 함수를 만들어보자.
게임보드의 한 행이 있을 때를 생각해보면, for문을 돌려 왼쪽 칸부터 확인하여 숫자면 왼쪽으로 밀어 수를 합치거나, 왼쪽으로 밀기만 할 것이다. 그리고 빈 칸(0)이면 패스하여 다음 칸(오른쪽 칸)을 확인할 것이다.
즉, 경우를 정리해보면 다음과 같다.
- 현재 칸이 빈 칸(0)이면 패스하기
- 현재 칸이 숫자 칸이면
- 왼쪽으로 밀기
- 왼쪽 수와 같은 수이면 합치기
이렇게 세 경우가 있음에 주의하여 함수를 구현해보면 다음과 같이 2중 for문으로 구현 가능하다.
def left_upd(board):
for i in range(n): # 행
# 숫자를 당겨올 위치 (혹은 합친 수를 놓을 위치)
cursor = 0
for j in range(1, n): # 열
# 현재 칸이 숫자이면
if board[i][j]:
tmp = board[i][j]
# ✅ 일단 비워질꺼니까 0으로 바꿈
board[i][j] = 0
# 커서 칸이 빈 칸이면 옮김
if not board[i][cursor]:
board[i][cursor] = tmp
# 커서 칸 수가 tmp와 같으면 합치고 커서 오른쪽으로 한 칸 이동
elif board[i][cursor] == tmp:
board[i][cursor] *= 2
cursor += 1
# 커서 칸이 숫자이고 tmp와 다르면, 커서 이동 후 숫자 옮김
else:
cursor += 1
board[i][cursor] = tmp
# ✅ board[i][j] = 0 여기 두면 안됨!
return board아마 주석과 함께 읽어보면 이해가 될 것이다.
주의할 점으로는, for>for>if문 내의 board[i][j] = 0을 뒤의 처리 뒤로 옮기면 안된다는 것이다. (위의 코드에서 앞의 ✅ 부분을 뒤의 ✅로 옮기면 안됨)
이유는 보드의 행이 이미 다른 숫자들로 가득 차있는 경우를 생각해보면 된다.
예를 들어 [2, 4, 8, 16] 으로 되어 있을 때, 이미 커서 위치(0)에 값이 차 있고 현재 칸(1)과 값이 다르니 else 로 빠질 것이다. 그럼 커서는 이동(1)하고 board[i][cursor] = tmp 가 되어 현재 위치가 된 커서 칸에 tmp 가 그대로 담길 것이다. 이대로 넘어가야 하는데 만약 뒤에 board[i][j] = 0 이 있으면 해당 칸이 0 이 되어 결국 [2, 8, 16, 0] 이런 식으로 변할 것이다.
위와 같이 left_upd() 만 잘 구현했다면, 다른 방향 밀기 또한 i, j 등의 인덱스 순서와 cursor 의 시작점만 다르기 때문에 쉽게 구현할 수 있다.
🍎 2. 5번 각각 미는 방향(조합)을 정하기
미는 방향을 5번 정하는 것은 백트래킹(DFS)을 이용하면 된다.
만약 백트래킹으로 푸는 것에 감이 안온다면 'BOJ. N과 M (3)' 문제를 먼저 풀어보자.
미는 방향 조합들을 백트래킹으로 먼저 구하여 배열에 정리해둔 후에 하나씩 꺼내어 위에서 만든 {방향}_upd() 함수를 실행해도 되고, 그냥 바로바로 실행해도 된다.
이번 풀이에서는 그냥 바로 실행하였다.
result = 0
def dfs(k, arr):
global result
if k == 5:
for i in range(n):
for j in range(n):
if arr[i][j] > result:
result = arr[i][j]
return
for i in range(4):
copy_arr = deepcopy(arr)
if i == 0:
dfs(k + 1, left_upd(copy_arr))
elif i == 1:
dfs(k + 1, right_upd(copy_arr))
elif i == 2:
dfs(k + 1, up_upd(copy_arr))
else:
dfs(k + 1, down_upd(copy_arr))
dfs(0, board)
print(result)📦 GitHub
해당 문제, 풀이에 대한 GitHub Repository 링크는 다음과 같다.
GitHub - 백준(Gold) '12100. 2048 (Easy)'
GitHub - [13강] 시뮬레이션/연습문제 '12100. 2048 (Easy)'
사실 처음에는 내가 처음에 풀었던 풀이와 '바킹독 알고리즘 [13강]'에서 알려주는 풀이를 비교 정리하기 위해 이 포스팅을 쓰고자 했다.
그런데 며칠 지나서 다시 보니 내가 처음에 풀었던 코드는 너무 더러워서 굳이 정리할 필요 없어보였다...ㅋㅋ
그래도 이 문제는 활용도 높은 풀이팁이 좀 많은 것 같아 정리를 해야겠다고 생각을 했다.
더러운 내 첫 풀이 코드를 정리하기엔 좀 아닌 것 같아서, 내 풀이와 같은 방식의 '🍎 1. 게임보드를 상하좌우 중 한 쪽으로 민 결과를 업데이트하기' 부분 풀이를 가진 (비교적) 클린한 코드를 참고하여 이번 포스팅에 정리하였다. [풀이 참고 링크]
정리하고 보니 은근 코드와 내용이 길어서 바킹독 풀이와 풀이팁들은 다음 포스팅에서 정리하기로 했다.
