알고리즘
파이썬) 2048(Easy) - BOJ
1일1공부실천하자
2023. 11. 11. 22:16
https://www.acmicpc.net/problem/12100
12100번: 2048 (Easy)
첫째 줄에 보드의 크기 N (1 ≤ N ≤ 20)이 주어진다. 둘째 줄부터 N개의 줄에는 게임판의 초기 상태가 주어진다. 0은 빈 칸을 나타내며, 이외의 값은 모두 블록을 나타낸다. 블록에 쓰여 있는 수는 2
www.acmicpc.net
from copy import deepcopy
n = int(input())
result = 0
arr = []
for _ in range(n):
arr.append(list(map(int, input().split())))
def check(board):
mm = 0
for i in board:
mm = max(max(i), mm)
return mm
def up(board):
visit = [[False for _ in range(n)] for _ in range(n)]
for i in range(n):
for j in range(n):
if board[i][j] == 0:
continue
else:
x = i
y = j
while True:
nx = x - 1
ny = y
if 0 <= nx < n and 0 <= ny < n:
if board[nx][ny] == 0:
board[nx][ny] = board[x][y]
board[x][y] = 0
visit[nx][ny] = visit[x][y]
visit[x][y] = False
x -= 1
elif board[nx][ny] == board[x][y] and visit[nx][ny] == False:
board[nx][ny] *= 2
visit[nx][ny] = True
board[x][y] = 0
x -= 1
else:
break
else:
break
def down(board):
visit = [[False for _ in range(n)] for _ in range(n)]
for i in range(n-1, -1, -1):
for j in range(n-1, -1, -1):
if board[i][j] == 0:
continue
else:
x = i
y = j
while True:
nx = x + 1
ny = y
if 0 <= nx < n and 0 <= ny < n:
if board[nx][ny] == 0:
board[nx][ny] = board[x][y]
board[x][y] = 0
visit[nx][ny] = visit[x][y]
visit[x][y] = False
x += 1
elif board[nx][ny] == board[x][y] and visit[nx][ny] == False:
board[nx][ny] *= 2
visit[nx][ny] = True
board[x][y] = 0
x += 1
else:
break
else:
break
def left(board):
visit = [[False for _ in range(n)] for _ in range(n)]
for i in range(n):
for j in range(n):
if board[i][j] == 0:
continue
else:
x = i
y = j
while True:
nx = x
ny = y - 1
if 0 <= nx < n and 0 <= ny < n:
if board[nx][ny] == 0:
board[nx][ny] = board[x][y]
board[x][y] = 0
visit[nx][ny] = visit[x][y]
visit[x][y] = False
y -= 1
elif board[nx][ny] == board[x][y] and visit[nx][ny] == False:
board[nx][ny] *= 2
visit[nx][ny] = True
board[x][y] = 0
y -= 1
else:
break
else:
break
def right(board):
visit = [[False for _ in range(n)] for _ in range(n)]
for i in range(n-1, -1, -1):
for j in range(n-1, -1, -1):
if board[i][j] == 0:
continue
else:
x = i
y = j
while True:
nx = x
ny = y + 1
if 0 <= nx < n and 0 <= ny < n:
if board[nx][ny] == 0:
board[nx][ny] = board[x][y]
board[x][y] = 0
visit[nx][ny] = visit[x][y]
visit[x][y] = False
y += 1
elif board[nx][ny] == board[x][y] and visit[nx][ny] == False:
board[nx][ny] *= 2
visit[nx][ny] = True
board[x][y] = 0
y += 1
else:
break
else:
break
def dfs(cnt, board, dir):
if cnt >= 6:
global result
result = max(result, check(board))
return
if dir == 0:
up(board)
elif dir == 1:
down(board)
elif dir == 2:
left(board)
else:
right(board)
cnt += 1
for i in range(4):
dfs(cnt, board, i)
for i in range(4):
b = deepcopy(arr)
dfs(0, b, i)
print(result)