https://www.acmicpc.net/problem/12100
2048 구현하는 문제이다. 최대 5회를 돌렸을 때 최대 값을 출력하는 것이 목표다.
방향이 4개이고 5회라서 모든 경우를 고려했을 때 1,024회 밖에 되지 않아서 DFS로 해결하기로 했다.
움직이기
def move(dir, board):
if dir == 0: # 좌
for i in range(n):
tmp = []
for j in range(n):
if tmp and board[i][j] and tmp[-1] == board[i][j]:
tmp[-1] *= -2
elif board[i][j]:
tmp.append(board[i][j])
for j in range(n):
board[i][j] = abs(tmp[j]) if j < len(tmp) else 0
elif dir == 1: # 우
for i in range(n):
tmp = []
for j in range(n-1, -1, -1):
if tmp and board[i][j] and tmp[-1] == board[i][j]:
tmp[-1] *= -2
elif board[i][j]:
tmp.append(board[i][j])
for j in range(n):
board[i][n-j-1] = abs(tmp[j]) if j < len(tmp) else 0
elif dir == 2: #좌
for j in range(n):
tmp = []
for i in range(n):
if tmp and board[i][j] and tmp[-1] == board[i][j]:
tmp[-1] *= -2
elif board[i][j]:
tmp.append(board[i][j])
for i in range(n):
board[i][j] = abs(tmp[i]) if i < len(tmp) else 0
elif dir == 3: #우
for j in range(n):
tmp = []
for i in range(n-1, -1, -1):
if tmp and board[i][j] and tmp[-1] == board[i][j]:
tmp[-1] *= -2
elif board[i][j]:
tmp.append(board[i][j])
for i in range(n):
board[n-i-1][j] = abs(tmp[i]) if i < len(tmp) else 0
return board좌우상하 순으로 조건을 부여했다.
각 행 또는 열 별로 tmp라는 빈 리스트를 선언 및 초기화하고 해당 라인에서 0이 아닌 숫자를 저장한다.
이때 같은 숫자가 반복되면 2를 곱해준다.
여기서 오류가 발생할 수 있는데
2240
이렇게 되어 있을 때 만약 왼쪽으로 이동한다면
4400
이 정상이지만 그냥 2를 곱하면
8000
으로 나오는 경우가 생긴다. 따라서 나는 -2를 곱해줘서 "얘는 이미 더해진 숫자"라는 표시를 해줬다.
tmp에 0이 아닌 숫자를 저장하는 과정이 끝나면 다시 해당 라인을 덮어야하는데 tmp에서 먼저 꺼내서 방향에 따라 저장하고, tmp에서 다 꺼냈으면 0으로 덮어씌운다.
이때 -2를 곱한 숫자는 절대값으로 저장되도록 했다.
DFS
def dfs(count, board):
if count == 5:
for b in board:
ans.append(max(b))
return
for d in range(4):
dfs(count+1, move(d, copy.deepcopy(board)))DFS는 이동 횟수를 저장할 count와 보드를 저장한 board를 입력받아서 count가 5라면 board 모든 행의 최대값을 ans라는 리스트에 저장한다. 더 최적화를 시킨다면 board의 최대값을 저장할 수도 있겠지만 시간초과 나면 고치려고 놔뒀는데 통과해서 그냥 뒀다.
5회가 아직 안 됐다면 for문을 돌면서 4가지 방향의 경우를 확인해주는데, 이때 board의 깊은 복사가 발생하도록 copy의 deepcopy를 불러와서 사용했다.
모든 과정이 끝나면 ans의 최대값을 불러와서 정답을 구했다.
코드
import copy
n = int(input())
board = [list(map(int, input().split())) for _ in range(n)]
def move(dir, board):
if dir == 0: # 좌
for i in range(n):
tmp = []
for j in range(n):
if tmp and board[i][j] and tmp[-1] == board[i][j]:
tmp[-1] *= -2
elif board[i][j]:
tmp.append(board[i][j])
for j in range(n):
board[i][j] = abs(tmp[j]) if j < len(tmp) else 0
elif dir == 1: # 우
for i in range(n):
tmp = []
for j in range(n-1, -1, -1):
if tmp and board[i][j] and tmp[-1] == board[i][j]:
tmp[-1] *= -2
elif board[i][j]:
tmp.append(board[i][j])
for j in range(n):
board[i][n-j-1] = abs(tmp[j]) if j < len(tmp) else 0
elif dir == 2: #좌
for j in range(n):
tmp = []
for i in range(n):
if tmp and board[i][j] and tmp[-1] == board[i][j]:
tmp[-1] *= -2
elif board[i][j]:
tmp.append(board[i][j])
for i in range(n):
board[i][j] = abs(tmp[i]) if i < len(tmp) else 0
elif dir == 3: #우
for j in range(n):
tmp = []
for i in range(n-1, -1, -1):
if tmp and board[i][j] and tmp[-1] == board[i][j]:
tmp[-1] *= -2
elif board[i][j]:
tmp.append(board[i][j])
for i in range(n):
board[n-i-1][j] = abs(tmp[i]) if i < len(tmp) else 0
return board
ans = []
def dfs(count, board):
if count == 5:
for b in board:
ans.append(max(b))
return
for d in range(4):
dfs(count+1, move(d, copy.deepcopy(board)))
dfs(0, board)
print(max(ans))
