[백준] 12100번 2048 (Easy) - python
문제보기
https://www.acmicpc.net/problem/12100
12100번: 2048 (Easy)
첫째 줄에 보드의 크기 N (1 ≤ N ≤ 20)이 주어진다. 둘째 줄부터 N개의 줄에는 게임판의 초기 상태가 주어진다. 0은 빈 칸을 나타내며, 이외의 값은 모두 블록을 나타낸다. 블록에 쓰여 있는 수는 2
www.acmicpc.net
풀이 & 코드
필자는 문제를 풀때 주로 공책을 사용한다. 어떤 방식이 좋을 지와 어떤 flow를 따라 코드를 짜야 효율적이지 등을 고민한다. 가장 먼저 떠오른 생각은 지정한 방향으로의 이동과 숫자 더하기 파트를 분리하는 것이었다. 그렇게 이동과 합치기를 하나의 노드라고 생각하고 재귀를 사용한 dfs방식으로 구현하였다. 참고로 재귀를 이용한 dfs/bfs는 재귀깊이에러를 발생할 가능성이 높지만 해당 문제는 가능한 방향(상하좌우) 4방향에 최대 depth 5를 고려하면 최대 방문 횟수가 20개이기에 재귀를 이용한 방식으로 구현하였다.
그렇다면 이동은 어떻게 구현을 할까. 먼저 왼쪽으로 이동하는 것을 생각해보자. 이것은 비교적 구현하기가 쉽다. 그저 숫자 중간에 끼여있는 0을 제거해 주면 숫자들이 왼쪽으로 이동하는 것과 같기 때문이다. 필자는 이 생각에 기인해 회전과 제거를 통해 지정한 방향으로의 이동을 구현하였다. board를 회전을 시켜 이동시켜주어야 할 방향을 왼쪽방향으로 바꾸고 0을 제거해주는 방식으로 코드를 작성했다.
이해가 안된다면 예시를 살펴보자! 만일 [[0,2,3],[4,0,6],[7,8,0]] 라는 board가 있고 이를 위쪽 방향으로 이동시키려고 한다. 그러면 먼저 board를 반시계 방향으로 회전시켜 [[3,6,0],[2,0,8],[0,4,7]]로 바꾼다. 그렇다면 원래 board에서의 위쪽방향이 해당 방향에서는 왼쪽으로 변했다! 그 이후에 0을 제거해 주면 왼쪽으로 이동하게 되는데, 원래 보드를 기준으로 본다면 위쪽방향으로 이동한 것과 같다!
[[0,2,3] , [[3,6,0], [[3,6],
[4,0,6], -> [2,0,8], -> [2,8],
[7,8,0]] [0,4,7]] [4,7]]
작업이 끝난 리스트를 시계방향으로 회전시키면 위방향으로의 이동과 같다! 그렇지만, 다시 시계방향으로 회전시켜 원래 모형으로 되돌리지는 않는다. dfs를 돌면서 다시 상하좌우 이동을 하기 때문에 의미가 없다. 우리는 결과값만 필요하고 중간 과정의 board는 필요없기 때문이다.
move라는 함수에 반시계방향 회전을 구현했고 cnt라는 파라미터를 이용해 방향 횟수로 상하좌우를 구현하였다.(0: 좌, 1 : 하, 2: 우, 3: 상) 또한 return을 할때 0이 아닌 값들만 리스트에 담아서 반환하도록 작성하였다. 사실 이 회전 부분이 가장 난해해보인다. 이 부분만 이해했다면 나머지는 쉽다..ㅠ
def move(board, cnt):
n = len(board)
for _ in range(cnt):
board = [[b[n-i-1] for b in board] for i in range(len(board))]
return [[el for el in b if el != 0] for b in board]
다음으로 합치기 부분이다. 이 합치기 부분은 left라는 변수를 활용하였다. for문으로 row안에 원소들을 탐색하면서 left가 없다면 left에 값을 주어준다. left가 있다면, 현재 원소랑 비교해 같으면 합치고 아닐 경우 left를 바꾸어주는 형태로 코드를 작성하였다. 또한 return할때 비어있는 만큼 0을 채워주고 반환하도록 작성하였다.
def combine(board):
n = len(board)
for r, row in enumerate(board):
left = None
combined = []
for el in row:
if left == None:
left = el
elif left == el:
combined.append(left + el)
left = None
else:
combined.append(left)
left = el
if left != None:
combined.append(left)
board[r] = combined
return [row + [0 for _ in range(n-len(row))] for row in board]
이제 핵심적인 함수는 다 작성하였다. dfs를 이용해 마무리만 지어주면 된다. depth가 5일때 board에서 최대값을 꺼내 반환하도록 작성하였고 for문과 방향을 나타내는 d변수를 통해 상하좌우에 맞춰 이동과 합치기 함수를 작동시켰다.
def dfs(board, depth):
answer = 0
if depth == 5:
M = max([max(b) for b in board])
return M
for d in range(4):
new_board = move(board, d)
new_board = combine(new_board)
result = dfs(new_board, depth+1)
answer = result if result > answer else answer
return answer
전체코드
n = int(input())
board = [list(map(int, input().split())) for _ in range(n)]
def move(board, cnt):
n = len(board)
for _ in range(cnt):
board = [[b[n-i-1] for b in board] for i in range(len(board))]
return [[el for el in b if el != 0] for b in board]
def combine(board):
n = len(board)
for r, row in enumerate(board):
left = None
combined = []
for el in row:
if left == None:
left = el
elif left == el:
combined.append(left + el)
left = None
else:
combined.append(left)
left = el
if left != None:
combined.append(left)
board[r] = combined
return [row + [0 for _ in range(n-len(row))] for row in board]
def dfs(board, depth):
answer = 0
if depth == 5:
M = max([max(b) for b in board])
return M
for d in range(4):
new_board = move(board, d)
new_board = combine(new_board)
result = dfs(new_board, depth+1)
answer = result if result > answer else answer
return answer
print(dfs(board, 0))