굉장히 까다로웠던 문제
골드 1인 구슬탈출이 훨씬 쉬운거같은데 왜 골2?
처음에는 아무생각없이 이렇게 코드를 짰다.
import sys
input = sys.stdin.readline
from copy import deepcopy
dy = [1,-1,0,0]
dx = [0,0,1,-1]
N = int(input())
board = []
for i in range(N):
board.append(list(map(int,input().split())))
def move(y,x,direction,copyboard):
num = copyboard[y][x]
copyboard[y][x] = 0
while True:
y1 = y+dy[direction]
x1 = x+dx[direction]
if not (N>y1>=0 and N>x1>=0):
break
if copyboard[y1][x1] == num:
copyboard[y1][x1] = num*2
return
if copyboard[y1][x1] != 0:
break
y,x = y1,x1
copyboard[y][x] = num
def moveall(board,direction):
copyboard = deepcopy(board)
if direction == 1 or direction == 2:
for i in range(N):
for j in range(N):
if copyboard[i][j] != 0:
move(i,j,direction,copyboard)
else:
for i in reversed(range(N)):
for j in reversed(range(N)):
if copyboard[i][j] != 0:
move(i,j,direction,copyboard)
return copyboard
finish = False
maxnum = 2
def check(board):
global finish,maxnum
SUM = 0
for i in range(N):
for j in range(N):
if board[i][j] != 0:
maxnum = max(maxnum,board[i][j])
SUM += board[i][j]
if SUM < maxnum*2:
finish = True
def game(board,cnt):
if finish:
return
if cnt == 5:
check(board)
return
for direction in range(4):
game(moveall(board,direction),cnt+1)
game(board,0)
print(maxnum)move함수를 만들어 모든 숫자를 제일 위에서부터 차례대로 방향대로 옮기고, 같은 숫자가 있으면 합쳐주는 방식이었다.
그러나 이 방식의 치명적인 문제점이 있었으니 바로 한번에 두번 합체하면 안된다는 것을 어겼다는 것이다.
즉 2 2 4 0을 왼쪽으로 옮길 경우, 4 4 0 0 이 되어야하는데, 내 방식은 8 0 0 0 이 되는 것이었다.
이걸 어떻게 구현해야할지 고민하다가 deque를 이용하기로 했다.
deque에 일렬로 문자를 쭉 담은 다음 뱉어내는 방식이다.
코드는 아래와 같다.
import sys
input = sys.stdin.readline
from copy import deepcopy
from collections import deque
dy = [1,-1,0,0]
dx = [0,0,1,-1]
N = int(input())
board = []
for i in range(N):
board.append(list(map(int,input().split())))
def move(board,direction):
copyboard = deepcopy(board)
for n in range(N):
dq = deque()
if direction == 0 or direction == 1:
for i in range(N):
if copyboard[i][n] != 0:
dq.append(copyboard[i][n])
copyboard[i][n] = 0
if direction == 0:
for i in reversed(range(N)):
if not dq:
break
copyboard[i][n] = dq.pop()
if not dq:
break
if copyboard[i][n] == dq[-1]:
copyboard[i][n] *= 2
dq.pop()
else:
for i in range(N):
if not dq:
break
copyboard[i][n] = dq.popleft()
if not dq:
break
if copyboard[i][n] == dq[0]:
copyboard[i][n] *= 2
dq.popleft()
else:
for i in range(N):
if copyboard[n][i] != 0:
dq.append(copyboard[n][i])
copyboard[n][i] = 0
if direction == 3:
for i in reversed(range(N)):
if not dq:
break
copyboard[n][i] = dq.pop()
if not dq:
break
if copyboard[n][i] == dq[-1]:
copyboard[n][i] *= 2
dq.pop()
else:
for i in range(N):
if not dq:
break
copyboard[n][i] = dq.popleft()
if not dq:
break
if copyboard[n][i] == dq[0]:
copyboard[n][i] *= 2
dq.popleft()
return copyboard
finish = False
maxnum = 2
def check(board):
global finish,maxnum
SUM = 0
for i in range(N):
for j in range(N):
if board[i][j] != 0:
maxnum = max(maxnum,board[i][j])
SUM += board[i][j]
if SUM < maxnum*2:
finish = True
def game(board,cnt):
if finish:
return
if cnt == 5:
check(board)
return
for direction in range(4):
game(move(board,direction),cnt+1)
game(board,0)
print(maxnum)사실 구현방식의 문제이지 아이디어는 특별할게 없다.
move함수를 deque를 이용해 구현하였고, 매번 move할때마다 deepcopy를 한 뒤 return하는 전형적인 DFS 방식이다.
이때 시간을 줄이기 위해서 보드의 모든 수의 합이 가장 큰수의 두배보다 작을 경우 코드를 종료하도록 했는데, 효과가 있었는지는 잘 모르겠다.
오늘의 교훈) 문제를 꼼꼼이 읽자!