문제
2048 게임은 4×4 크기의 보드에서 혼자 즐기는 재미있는 게임이다.
이 게임에서 한 번의 이동은 보드 위에 있는 전체 블록을 상하좌우 네 방향 중 하나로 이동시키는 것이다. 이때, 같은 값을 갖는 두 블록이 충돌하면 두 블록은 하나로 합쳐지게 된다. 한 번의 이동에서 이미 합쳐진 블록은 또 다른 블록과 다시 합쳐질 수 없다. (실제 게임에서는 이동을 한 번 할 때마다 블록이 추가되지만, 이 문제에서 블록이 추가되는 경우는 없다)
이 문제에서 다루는 2048 게임은 보드의 크기가 N×N 이다. 보드의 크기와 보드판의 블록 상태가 주어졌을 때, 최대 5번 이동해서 만들 수 있는 가장 큰 블록의 값을 구하는 프로그램을 작성하시오.
풀이
문제에서 말한대로 방향을 옮겨가며 합치기 연산을 수행하면 되는 문제다. 4방향에 대해서 각각의 연산을 실행해야하고 그 연산을 실행하고난 값에 또 4방향에 대한 연산을 실행해야하고 그게 5번반복되고 나면 그때의 최댓값을 구해주면된다.
그렇다는 것은 4방향에 대해 DFS를 실행하고 그 depth가 5가되면 변수에 저장된 최대값을 갱신해주는 방식으로 구현할 수 있다는 얘기다.
처음에는 어마무시하게 무식하게 이 문제를 풀었다. 각 방향에 대해서 합치기 연산과정과 이동시키는 과정을 따로 분리해서 구현하였고 이로인해 코드길이는 물론 실행시간도 엄청나게 늘어났다(이전버전 1200ms, 개선버전 456ms).
코드를 개선하기 위해 찾아보니 이 두가지를 모두 한번의 for루프로 할 수 있다는 사실을 알게 됐고 개선한 코드도 아래에 첨부한다.
무식하게 풀기 버전
import copy
N = int(input())
initial_graph = [list(map(int, input().split())) for _ in range(N)]
answer = 0
def push_biggest_block_to_answer(depth:int, cur_graph:list[list[int]]) -> None:
global answer
if depth == 5:
answer = max(answer , max(map(max, cur_graph)))
return
for i in range(4):
if i == 0:
graph = copy.deepcopy(cur_graph)
for row in range(N):
for col in range(-1, -N, -1):
change_col = col-1
while change_col > -N and graph[row][change_col] == 0:
change_col -=1
if change_col < -N: break
if graph[row][col] == graph[row][change_col]:
graph[row][col] *= 2
graph[row][change_col] = 0
for col in range(-1, -(N+1), -1):
change_col = col-1
if graph[row][col] == 0:
while change_col > -N and graph[row][change_col] == 0:
change_col -= 1
if change_col < -N: break
graph[row][col], graph[row][change_col] = graph[row][change_col], graph[row][col]
push_biggest_block_to_answer(depth+1, graph)
elif i == 1:
graph = copy.deepcopy(cur_graph)
for row in range(N):
for col in range(N-1):
change_col = col + 1
while change_col < N and graph[row][change_col] == 0:
change_col +=1
if change_col >= N: break
if graph[row][col] == graph[row][change_col]:
graph[row][col] *= 2
graph[row][change_col] = 0
for col in range(N):
change_col = col+1
if graph[row][col] == 0:
while change_col < N and graph[row][change_col] == 0:
change_col +=1
if change_col >= N: break
graph[row][col], graph[row][change_col] = graph[row][change_col], graph[row][col]
push_biggest_block_to_answer(depth+1, graph)
elif i == 2:
graph = copy.deepcopy(cur_graph)
for col in range(N):
for row in range(-1, -N, -1):
change_row = row -1
while change_row > -N and graph[change_row][col] == 0:
change_row -= 1
if change_row < -N: break
if graph[row][col] == graph[change_row][col]:
graph[row][col] *= 2
graph[change_row][col] = 0
for row in range(-1, -(N+1), -1):
change_row = row-1
if graph[row][col] == 0:
while change_row > -N and graph[change_row][col] == 0:
change_row -= 1
if change_row < -N:
break
graph[row][col], graph[change_row][col] = graph[change_row][col], graph[row][col]
push_biggest_block_to_answer(depth+1, graph)
elif i == 3:
graph = copy.deepcopy(cur_graph)
for col in range(N):
for row in range(N-1):
change_row = row+1
while change_row < N and graph[change_row][col] == 0:
change_row +=1
if change_row >= N: break
if graph[row][col] == graph[change_row][col]:
graph[row][col] *= 2
graph[change_row][col] = 0
for row in range(N):
change_row = row+1
if graph[row][col] == 0:
while change_row < N and graph[change_row][col] == 0:
change_row +=1
if change_row >= N: break
graph[row][col], graph[change_row][col] = graph[change_row][col], graph[row][col]
push_biggest_block_to_answer(depth+1, graph)
push_biggest_block_to_answer(0, initial_graph)
print(answer)개선 코드
from copy import deepcopy
import sys
sys.stdin = open('/Users/jujeonghan/Developer/camp/algorithm_study/시뮬레이션/test.txt', 'r')
N = int(input())
initial_graph = [list(map(int, input().split())) for _ in range(N)]
answer = 0
def right_move(graph:list[list[int]]):
for row in range(N):
change_col = N-1
for col in range(N-1, -1, -1):
if graph[row][col]:
cur_value = graph[row][col]
graph[row][col] = 0
if graph[row][change_col] == 0:
graph[row][change_col] = cur_value
elif graph[row][change_col] == cur_value:
graph[row][change_col] *= 2
change_col-=1
else:
change_col-=1
graph[row][change_col] = cur_value
return graph
def left_move(graph:list[list[int]]):
for row in range(N):
change_col = 0
for col in range(1, N):
if graph[row][col]:
cur_value = graph[row][col]
graph[row][col] = 0
if graph[row][change_col] == 0:
graph[row][change_col] = cur_value
elif graph[row][change_col] == cur_value:
graph[row][change_col] *=2
change_col+=1
else:
change_col+=1
graph[row][change_col] = cur_value
return graph
def down_move(graph:list[list[int]]):
for col in range(N):
change_row = N-1
for row in range(N-1, -1, -1):
if graph[row][col]:
cur_value = graph[row][col]
graph[row][col] = 0
if graph[change_row][col] == 0:
graph[change_row][col] = cur_value
elif graph[change_row][col] == cur_value:
graph[change_row][col] *=2
change_row -=1
else:
change_row-=1
graph[change_row][col] = cur_value
return graph
def up_move(graph:list[list[int]]):
for col in range(N):
change_row = 0
for row in range(1, N):
if graph[row][col]:
cur_value = graph[row][col]
graph[row][col] = 0
if graph[change_row][col] == 0:
graph[change_row][col] = cur_value
elif graph[change_row][col] == cur_value:
graph[change_row][col] *=2
change_row +=1
else:
change_row+=1
graph[change_row][col] = cur_value
return graph
def update_biggest_block(depth:int, cur_graph:list[list[int]]) -> None:
global answer
if depth == 5:
answer = max(answer , max(map(max, cur_graph)))
return
update_biggest_block(depth+1, right_move(deepcopy(cur_graph)))
update_biggest_block(depth+1, left_move(deepcopy(cur_graph)))
update_biggest_block(depth+1, up_move(deepcopy(cur_graph)))
update_biggest_block(depth+1, down_move(deepcopy(cur_graph)))
update_biggest_block(0, initial_graph)
print(answer)
내 것인 줄 알았으나 받은 모든 것이 선물이었다.