보드는 동서남북으로 기울일 수 있으므로 임의로 각 방향마다 0~4까지 번호를 정해주었다.
그리고 미리 가능한 방향들의 경우의 수를 모두 구한 후에 그대로 기울여본 후 최대값을 갱신하는 방식으로 진행했다.
가능한 방향들의 경우의 수를 구하는 방법은, 뽑을 수 있는 가짓수(방향)는 4개이고 총 5개를 뽑아야 하므로 4개 중 5개를 중복을 허용하는 순열로 뽑았다. 기울이는 순서에 따라 결과도 달라지므로 조합이 아니라 순열로 뽑아야 한다.
한 가지 방향으로 기울이는 방법만 알면 나머지 방향은 조금씩만 수정하면 되므로, 위로 기울이는 방법을 보자.
위로 기울인다는 것은 (0, 0) 원소 입장에서 (1, 0) 에 있는 원소들을 땡겨온다는 뜻이다.
여기서 두 케이스가 있을 수 있다. 기준 원소 (0, 0)의 값이 0인 케이스와 0이 아닌 케이스가 있을 수 있다.
먼저 값이 0이면 다음 행에 있는 것들 중 0이 아닌 값을 찾아서 가져와야 한다. 즉, 먼저 밀어주어야 한다.
이제 기준 원소의 값이 0이 아니게 되었으면, 거기서부터 다시 그 다음 행에서 0이 아닌 값들을 가져와서 비교한다.
비교해서 같은 값이면 합쳐준다. 다른 값이면 아무 행동도 하지 않는다. 어차피 다음 반복문에서 그 원소를 땡겨오거나 사용하게 될 것이다.
남쪽으로 밀어줄 때는 기준 원소가 0에서 시작하는 것이 아니라 N-1에서 시작해서 1로 끝난다는 점이 달라진다.
마지막이 (1, y)가 되고 비교 원소가 (0, y)가 될 것이므로 마지막 row가 0이 아닌 1이 된다. 마지막 row를 0으로 두면 그 다음 비교 원소가 -1이 되므로, out of index가 되거나 비교문을 한번 넣어줘야 한다.
주의해야 할 점은 한 번의 기울임마다 두 번 합쳐질 수 없다는 뜻이지, 한번 합쳐진 원소는 두번 다시 못 합쳐진다는 뜻이 아니므로 한번 기울여진 적이 있음을 체크하는 배열을 계속 초기화해줘야 된다는 점이다. (여기서는 added를 계속 새로 선언했다.)
import sys
from copy import deepcopy
def solve(selected):
board = deepcopy(board_o)
for direct in selected:
added = [[False for _ in range(N)] for _ in range(N)]
if direct == 0: # UP
for r in range(N-1):
for c in range(N):
next_r = r + 1
# 기준 원소의 값이 0일 때 -> 0이 아닌 값을 찾아서 땡겨온다.
if board[r][c] == 0:
while next_r < N:
if board[next_r][c] == 0:
next_r += 1
else:
board[r][c] = board[next_r][c]
board[next_r][c] = 0
break
# 기준 원소의 값이 0이 아닐 때 -> 다음 줄에 있는 원소 중 0이 아닌 것을 땡겨온다.
while next_r < N:
if board[next_r][c] == 0:
next_r += 1
else: # 0이 아닌 것을 땡겨 왔으면 비교 후 같으면 합쳐준다.
if board[r][c] == board[next_r][c] \
and not added[next_r][c] and not added[r][c]:
board[r][c] = board[r][c] * 2
board[next_r][c] = 0
added[r][c] = True
added[next_r][c] = False
break
elif direct == 1: # DOWN
for r in reversed(range(1, N)):
for c in range(N):
next_r = r - 1
if board[r][c] == 0:
while next_r >= 0:
if board[next_r][c] == 0:
next_r -= 1
else:
board[r][c] = board[next_r][c]
board[next_r][c] = 0
break
while next_r >= 0:
if board[next_r][c] == 0:
next_r -= 1
else:
if board[r][c] == board[next_r][c] \
and not added[next_r][c] and not added[r][c]:
board[r][c] = board[r][c] * 2
board[next_r][c] = 0
added[r][c] = True
added[next_r][c] = False
break
elif direct == 2: # LEFT
for r in range(N):
for c in range(N - 1):
next_c = c + 1
if board[r][c] == 0:
while next_c < N:
if board[r][next_c] == 0:
next_c += 1
else:
board[r][c] = board[r][next_c]
board[r][next_c] = 0
break
while next_c < N:
if board[r][next_c] == 0:
next_c += 1
else:
if board[r][c] == board[r][next_c] \
and not added[r][next_c] and not added[r][c]:
board[r][c] = board[r][c] * 2
board[r][next_c] = 0
added[r][c] = True
added[r][next_c] = False
break
elif direct == 3: # Right
for r in range(N):
for c in reversed(range(1, N)):
next_c = c - 1
if board[r][c] == 0: # 땡기기
while next_c >= 0:
if board[r][next_c] == 0:
next_c -= 1
else:
board[r][c] = board[r][next_c]
board[r][next_c] = 0
break
while next_c >= 0:
if board[r][next_c] == 0:
next_c -= 1
else:
if board[r][c] == board[r][next_c] \
and not added[r][next_c] and not added[r][c]:
board[r][c] = board[r][c] * 2
board[r][next_c] = 0
added[r][c] = True
added[r][next_c] = False
break
ret = max([max(r) for r in board])
return ret
def dfs(count, selected):
global maxRet
if count == 5:
maxRet = max(maxRet, solve(selected))
return
for i in range(4):
dfs(count+1, selected+[i])
return maxRet
maxRet = 0
input = sys.stdin.readline
N = int(input())
board_o = [list(map(int, input().split())) for _ in range(N)]
print(dfs(0, []))
'알고리즘 > 브루트포스' 카테고리의 다른 글
16637. 괄호 추가하기 (2) (0) | 2020.05.12 |
---|---|
16637번. 괄호 추가하기 (0) | 2020.05.11 |
17609번. 회문 (0) | 2020.04.19 |
12100. 2048 (Easy) (0) | 2020.01.07 |
2231. 분해합 (0) | 2019.11.20 |