문제 풀기 : 12100번
문제
한 번의 이동은 보드 위에 있는 전체 블록을 상하좌우 네 방향 중 하나로 이동시킨다.
같은 값을 갖는 두 블록이 충돌하면 두 블록은 하나로 합쳐지게 된다.
한 번의 이동에서 이미 합쳐진 블록은 또 다른 블록과 다시 합쳐질 수 없다. (실제 게임에서는 이동을 한 번 할 때마다 블록이 추가되지만, 이 문제에서 블록이 추가되는 경우는 없다)
보드의 크기는 N×N 이다.
보드의 크기와 보드판의 블록 상태가 주어졌을 때, 최대 5번 이동해서 만들 수 있는 가장 큰 블록의 값을 구하라.
문제 풀이
이 문제는 dfs, bfs 둘 다 사용해서 풀 수 있는 문제로 필자는 dfs로 접근해서 문제를 풀었다.
dfs 코드 작성은 쉽다. 상, 하, 좌, 우로 dfs를 돌리고 5번을 다 돌렸을 때 배열에서 가장 큰 값의 요소를 리턴해주면 4방향의 리턴값들 중 다시 최대값을 리턴하는 것이다.(deepcopy 이용)
가장 어려웠던 부분은 4방향으로 움직이는 함수들을 만드는 것이었다.
이 문제의 핵심은 4가지 방향 조건으로 함수를 나누는 것인것 같다.
위로 움직였을 때의 상태를 예시로 들자면, 열순으로 두번째 행부터 탐색해주어야 한다. 이렇게 해주는 이유는 포인터를 사용하기 위함이다. 포인터는 가장 맨 앞쪽부터 위치해서 포인터가 가리키는 숫자들과 탐색되어지는 숫자들을 비교해 값을 변경하는 용도를 쓰여질 것이다.
다른 방향들도 마찬가지로 변경되는 값만 바꿔주면 된다.
정답 코드
import sys
from copy import deepcopy
input=sys.stdin.readline
n=int(input())
a=[list(map(int, input().split())) for _ in range(n)]
def DFS(board, cnt):
if cnt==5:
return max(map(max, board))
# 상, 하, 좌, 우로 움직여 리턴한 값들 중 가장 큰 값 반환
# board를 꼭 deepcopy하여 함수를 거친 board값이 다음 함수에 들어가지 못하도록 해주어야 한다.
return max(DFS(up(deepcopy(board)), cnt + 1), DFS(down(deepcopy(board)), cnt + 1), DFS(left(deepcopy(board)), cnt + 1), DFS(right(deepcopy(board)), cnt + 1))
def up(board):
for j in range(n):
pointer=0
for i in range(1,n):
if board[i][j]:
tmp=board[i][j]
board[i][j]=0
if board[pointer][j]==0:
board[pointer][j]=tmp
elif board[pointer][j]==tmp:
board[pointer][j] *=2
pointer +=1
else:
pointer +=1
board[pointer][j]=tmp
return board
def down(board):
for j in range(n):
pointer=n-1
for i in range(n-2, -1, -1):
if board[i][j]:
tmp=board[i][j]
board[i][j]=0
if board[pointer][j]==0:
board[pointer][j] = tmp
elif board[pointer][j] == tmp :
board[pointer][j] *= 2
pointer-=1
else:
pointer-=1
board[pointer][j]=tmp
return board
# LEFT
def left(board):
for i in range(n):
pointer = 0
for j in range(1, n):
if board[i][j]:
tmp = board[i][j]
board[i][j] = 0
if board[i][pointer] == 0:
board[i][pointer] = tmp
elif board[i][pointer] == tmp:
board[i][pointer] *= 2
pointer += 1
else:
pointer += 1
board[i][pointer]= tmp
return board
# RIGHT
def right(board):
for i in range(n):
pointer = n - 1
for j in range(n - 2, -1, -1):
if board[i][j]:
tmp = board[i][j]
board[i][j] = 0
if board[i][pointer] == 0:
board[i][pointer] = tmp
elif board[i][pointer] == tmp:
board[i][pointer] *= 2
pointer -= 1
else:
pointer -= 1
board[i][pointer] = tmp
return board
print(DFS(a,0))함수 설명
# LEFT
def left(board):
for i in range(n):
pointer = 0
for j in range(1, n):
if board[i][j]: # 0이 아닌 값이
tmp = board[i][j]
board[i][j] = 0 # 일단 비워질꺼니까 0으로 바꿈
if board[i][pointer] == 0: # 비어있으면
board[i][pointer] = tmp # 옮긴다
elif board[i][pointer] == tmp: #같으면 ex)2,2
board[i][pointer] *= 2 # 합친다
pointer += 1
else: # 비어있지도 않고 다른 값일때
pointer += 1 #pass
board[i][pointer]= tmp먼저 블록을 이동시키는 코드.
나머지 상, 하, 우 방법도 비슷하므로 좌로 움직일 때 코드만 설명.
설명은 주석으로 하는게 편할 거 같아서 주석으로 간단하게 작성했다.
옮길 블록은 board[i][j], 옮길 블록과 바꿀 자리는 board[i][pointer]이다.
