두가지 의문이 있었다.
5번만 진행하면 되기 때문에 dfs를 하면 최대 5개의 배열 복사본이 생긴다.
그렇기 때문에 메모리 초과를 걱정하지 않아도 된다.
🤔 그럼 어떻게 각 행과 열을 합칠 것인가?
from collections import deque
from sys import stdin
mx = -1
n = int(input())
a = [list(map(int, stdin.readline().rstrip().split())) for _ in range(n)]
q = deque()
def get(i, j):
if a[i][j]:
q.append(a[i][j])
a[i][j] = 0
def merge(i, j, di, dj):
while q:
val = q.popleft()
if not a[i][j]:
a[i][j] = val
# 다음 원소는 아직들어가지 않았으므로 a[i+di][j+dj] == 0이다..
elif a[i][j] == val:
a[i][j] = val * 2
i, j = i + di, j + dj
else:
i += di
j += dj
a[i][j] = val
def move(k):
if k == 0: # Up 이면 위로 숫자를 모으면서 점점 밑으로 내려오는 구조이다.
for j in range(n):
for i in range(n):
get(i, j) # 큐에 블럭을 담는 함수
merge(0, j, 1, 0) # 큐에 담은 블럭을 합치는 함수
elif k == 1: # down
for j in range(n):
for i in range(n-1, -1, -1): # 순서도 반대가 된다.
get(i, j)
merge(n - 1, j, -1, 0)
elif k == 2: # left
for i in range(n):
for j in range(n):
get(i, j)
merge(i, 0, 0, 1)
elif k == 3: # right
for i in range(n):
for j in range(n-1, -1, -1):
get(i, j)
merge(i, n - 1, 0, -1)
def dfs(index):
global mx, a
if index == 5:
for i in range(n):
mx = max(mx, max(a[i]))
return
b = [tmp[:] for tmp in a] # 복사 시 사용
for i in range(4):
move(i)
dfs(index + 1)
a = [tmp[:] for tmp in b]
dfs(0)
print(mx)
rebas님 블로그