문제
2048 게임은 4×4 크기의 보드에서 혼자 즐기는 재미있는 게임이다. 이 링크를 누르면 게임을 해볼 수 있다.
이 게임에서 한 번의 이동은 보드 위에 있는 전체 블록을 상하좌우 네 방향 중 하나로 이동시키는 것이다. 이때, 같은 값을 갖는 두 블록이 충돌하면 두 블록은 하나로 합쳐지게 된다. 한 번의 이동에서 이미 합쳐진 블록은 또 다른 블록과 다시 합쳐질 수 없다. (실제 게임에서는 이동을 한 번 할 때마다 블록이 추가되지만, 이 문제에서 블록이 추가되는 경우는 없다)
<그림 1>의 경우에서 위로 블록을 이동시키면 <그림 2>의 상태가 된다. 여기서, 왼쪽으로 블록을 이동시키면 <그림 3>의 상태가 된다.
<그림 4>의 상태에서 블록을 오른쪽으로 이동시키면 <그림 5>가 되고, 여기서 다시 위로 블록을 이동시키면 <그림 6>이 된다. 여기서 오른쪽으로 블록을 이동시켜 <그림 7>을 만들 수 있다.
<그림 8>의 상태에서 왼쪽으로 블록을 옮기면 어떻게 될까? 2가 충돌하기 때문에, 4로 합쳐지게 되고 <그림 9>의 상태가 된다.
<그림 10>에서 위로 블록을 이동시키면 <그림 11>의 상태가 된다.
<그림 12>의 경우에 위로 블록을 이동시키면 <그림 13>의 상태가 되는데, 그 이유는 한 번의 이동에서 이미 합쳐진 블록은 또 합쳐질 수 없기 때문이다.
마지막으로, 똑같은 수가 세 개가 있는 경우에는 이동하려고 하는 쪽의 칸이 먼저 합쳐진다. 예를 들어, 위로 이동시키는 경우에는 위쪽에 있는 블록이 먼저 합쳐지게 된다. <그림 14>의 경우에 위로 이동하면 <그림 15>를 만든다.
이 문제에서 다루는 2048 게임은 보드의 크기가 N×N 이다. 보드의 크기와 보드판의 블록 상태가 주어졌을 때, 최대 5번 이동해서 만들 수 있는 가장 큰 블록의 값을 구하는 프로그램을 작성하시오.
문제 풀이
각 방향으로 기울여서 미는것은 그래프를 회전하고 한 방향으로 미는것으로 생각하자.
- 미는 것은 왼쪽으로 미는것으로 통일.
- 그래프를 회전시키고 한 쪽으로 밀어도 상, 하, 좌, 우 로 미는 것을 표현할 수 있다.
def rotation_90(arr):
temp = [[0 for _ in range(n)] for _ in range(n)]
for i in range(n):
for j in range(n):
temp[j][n - i - 1] = arr[i][j]
return temp
def dfs(depth, graph):
global result
if depth == 5: # 5번 이동했다면 그때의 최대값을 비교.
for i in range(n):
x = max(graph[i])
if result < x:
result = x
return
for _ in range(4): # 총 4번 회전해야하니까
array = rotation_90(graph) # 회전
temp = [[0 for _ in range(n)] for _ in range(n)] # 임시 보드
for i in range(n): # 각 행을 기준으로
temp_idx = 0
for j in range(n):
if array[i][j] == 0: # 만약 게임보드의 값이 0이면 다음 column 조사
continue
if temp[i][temp_idx] == 0: # 임시 보드의 idx번째 값이 0이면
temp[i][temp_idx] = array[i][j] # 임시 보드의 idx번째 값을 채움
elif temp[i][temp_idx] == array[i][j]: # 임시 보드의 temp_idx 값과 보드의 값이 같으면
temp[i][temp_idx] = temp[i][temp_idx] * 2 # 합치기
temp_idx += 1 # 임시 보드의 칸은 오른쪽으로 한 칸 이동
elif temp[i][temp_idx] != array[i][j]: # 임시 보드의 값과 보드의 값이 다르면
temp_idx += 1 # 임시 보드의 칸은 오른쪽으로 한 칸 이동
temp[i][temp_idx] = array[i][j] # 이동한 임시 보드의 칸에 값을 추가.
graph = temp # 게임 보드를 한 번 회전한 것에 대하여 왼쪽으로 쭉 밀었을때의 결과로 바꾸기
dfs(depth + 1, graph) # 다음 이동 조사
graph = array # 게임 보드를 다시 되돌리기
if __name__ == "__main__":
n = int(input())
graph = [list(map(int, input().split())) for _ in range(n)]
result = 0
dfs(0, graph)
print(result)임시보드(temp)와 게임보드(array)의 관계를 설명하자면(line25~40)
하나의 행에서 왼쪽으로 밀었을 때 합쳐지는 과정을 봐보자.
- 처음 상태
array : 0 2 0 2 8 8 0 16
temp : 0 0 0 0 0 0 0 0
temp_idx = 0
-
array의 0번째 인덱스 값은 0이므로 Pass
1번째 값은 2이므로 temp의 0번째 값이 아직 없으므로 추가.array : 0 2 0 2 8 8 0 16
temp : 2 0 0 0 0 0 0 0
temp_idx = 0 -
array의 4번째 인덱스 값이 2
temp의 0번째 값과 동일하므로temp[0] * 2해준다.
이후temp_idx += 1array : 0 2 0 2 8 8 0 16
temp : 4 0 0 0 0 0 0 0
temp_idx = 1 -
array의 4번째 인덱스 값이 8.
temp의 temp_idx (1) 값이 0이므로 추가.array : 0 2 0 2 8 8 0 16
temp : 4 8 0 0 0 0 0 0
temp_idx = 1 -
array의 5번째 인덱스 값이 8
temp의 temp_idx (1) 값과 동일하므로temp[0] * 2
이후temp_idx += 1array : 0 2 0 2 8 8 0 16
temp : 4 16 0 0 0 0 0 0
temp_idx = 2
- array의 7번째 인덱스 값이 16
temp의 temp_dix (2) 값이 0이므로 추가.array : 0 2 0 2 8 8 0 16
temp : 4 16 16 0 0 0 0 0
temp_idx = 2
문제에서 "한 번의 이동에서 이미 합쳐진 블록은 또 다른 블록과 다시 합쳐질 수 없다." 라고 설명함.
이를 해결하기 위해서 1. temp와 array의 값이 같아서 숫자가 합쳐지거나 , 2. temp와 array의 값이 달라서 합쳐지지 않을 때는 temp의 idx를 늘리는 방법 선택.
이후 게임 보드(graph)를 한 번 회전한 것에 대하여 왼쪽으로 쭉 밀었을때의 결과(temp)로 바꿔주고 다시 dfs 함수 시작.
총 5번의 이동이 끝난 이후에는 게임 보드(graph)를 다시 되돌려서 다른 이동에 대해 조사.
