백준 문제 중 12100번, 구현, ‘2048(Easy)’
백준 문제 중 12100번
https://www.acmicpc.net/problem/12100
2048 게임은 4×4 크기의 보드에서 혼자 즐기는 재미있는 게임이다. 이 링크를 누르면 게임을 해볼 수 있다.
이 게임에서 한 번의 이동은 보드 위에 있는 전체 블록을 상하좌우 네 방향 중 하나로 이동시키는 것이다. 이때, 같은 값을 갖는 두 블록이 충돌하면 두 블록은 하나로 합쳐지게 된다. 한 번의 이동에서 이미 합쳐진 블록은 또 다른 블록과 다시 합쳐질 수 없다. (실제 게임에서는 이동을 한 번 할 때마다 블록이 추가되지만, 이 문제에서 블록이 추가되는 경우는 없다)
입력
첫째 줄에 보드의 크기 N (1 ≤ N ≤ 20)이 주어진다. 둘째 줄부터 N개의 줄에는 게임판의 초기 상태가 주어진다. 0은 빈 칸을 나타내며, 이외의 값은 모두 블록을 나타낸다. 블록에 쓰여 있는 수는 2보다 크거나 같고, 1024보다 작거나 같은 2의 제곱꼴이다. 블록은 적어도 하나 주어진다.
출력
최대 5번 이동시켜서 얻을 수 있는 가장 큰 블록을 출력한다.
풀이
처음에 문제에 접근 할때는 0이아닌 숫자가 있는 부분만 시작점으로 큐에 저장했다가 하나씩 꺼내서 한방향으로 모든 숫자를 이동하거나 병합하도록 진행하고 그 이후 남은 0이아닌 숫자를 큐에 넣어 BFS를 하는식으로 시도했었다.
그러나 코드를 짜다보니 맵 전체의 상태를 저장해야 될 필요성을 느꼈고 이동횟수가 5회로 제한되어 있으므로, 맵 전체를 입력 출력으로 하는 DFS를 하는게 더 나을 것 같다는 생각이 들었다.
여기 까지는 접근했으나 이동시 병합하거나 병합하지 않고 차례로 쌓는 처리가 너무 어려워서 검색을 통해 해결했다.
코드의 흐름은 이렇다.
- 현재 맵 상태를 입력으로 네 방향으로의 탐색을 재귀적으로 진행할 dfs를 호출한다.
- 한 방향에 대하여 이동할때 조건에 따라 블럭들을 병합하거나, 블럭들을 순차적으로 쌓는 처리를 해줄 함수 move를 호출한다.
- move 함수는 움직이기전 상태의 맵을 입력받아 움직이고 난 후의 상태의 맵을 출력한다.(이때 반드시 깊은복사로 맵을 넘겨주어야 한다.)
- dfs의 탐색이 5회가 되면 가능한 최대값을 구한다.
move 함수의 구현이 어려웠다. move 함수를 더 구체적으로 살펴보자
dir이 0인 경우 즉 위로 이동하는 경우라 가정하자.
- 맵을 각 col으로 쪼개 하나의 col마다 탐색을 진행하다.
- j번째 순차의 col의 가장 위를 기준으로 병합 및 저장이 시작되므로 열의 가장 윗 부분 row 인덱스인 0을 top에 저장한다.
- top이후의 인덱스 1부터 n-1을 i라 할때 차례대로 살펴보자.
- board[top][j]에 따라 top과 board[top][j]를 조작한다.
세가지의 동작이 있을 것이다.
- board[top][j] == 0 이라면 board[i][j] 를 board[top][j]에 대입한다. top은 변동이 없다.
- board[top][j] == board[i][j] 라면 병합이 가능하므로 board[top][j]에 병합을 해주고 한 이동에 한번의 병합만이 가능하므로 기준 top의 인덱스를 1 증가 시킨다.
- 둘다 아니라면 top의 인덱스를 1증가시키고 board[top][j]에 board[i][j]를 대입한다. (블럭이 쌓이는 경우)
이러한 과정을 각 방향에 대해 맞게끔 코드를 구성하면 된다.
from typing import List
from copy import deepcopy
n = int(input())
board = []
for _ in range(n):
board.append(list(map(int, input().split())))
def move(dir:int, board:List[List[int]])->List[List[int]]:
# up
if dir == 0:
for j in range(n):
top = 0
for i in range(1, n):
if board[i][j] != 0:
tmp = board[i][j]
board[i][j] = 0
if board[top][j] == 0:
board[top][j] = tmp
elif board[top][j] == tmp:
board[top][j] = tmp * 2
top += 1
else:
top += 1
board[top][j] = tmp
# right
elif dir == 1:
for i in range(n):
top = n - 1
for j in range(n - 2, -1, -1):
if board[i][j] != 0:
tmp = board[i][j]
board[i][j] = 0
if board[i][top] == 0:
board[i][top] = tmp
elif board[i][top] == tmp:
board[i][top] = tmp * 2
top -= 1
else:
top -= 1
board[i][top] = tmp
# down
elif dir == 2:
for j in range(n):
top = n - 1
for i in range(n - 2, -1, -1):
if board[i][j] != 0:
tmp = board[i][j]
board[i][j] = 0
if board[top][j] == 0:
board[top][j] = tmp
elif board[top][j] == tmp:
board[top][j] = tmp * 2
top -= 1
else:
top -= 1
board[top][j] = tmp
# left
elif dir == 3:
for i in range(n):
top = 0
for j in range(1, n):
if board[i][j] != 0:
tmp = board[i][j]
board[i][j] = 0
if board[i][top] == 0:
board[i][top] = tmp
elif board[i][top] == tmp:
board[i][top] = tmp * 2
top += 1
else:
top += 1
board[i][top] = tmp
return board
ans = 0
def dfs(board:List[List[int]], cnt:int)->int:
global ans
if cnt == 5:
for i in range(n):
for j in range(n):
ans = max(ans, board[i][j])
return
dfs(move(0,deepcopy(board)), cnt +1)
dfs(move(1,deepcopy(board)), cnt +1)
dfs(move(2,deepcopy(board)), cnt +1)
dfs(move(3,deepcopy(board)), cnt +1)
dfs(board, 0)
print(ans)
3
2 0 2
0 2 0
2 0 2
4
배운점
내가 슬라이싱 복사에 대해 잘못 알고 있어 헤맸던 부분이 있다. [:] 통한 객체 복사는 엄밀히 말하면 얕은 복사라는것이다. 처음에는 copy 모듈의 deepcopy가 아닌 슬라이싱 [:]을 통해 맵을 넘겨주었는데 굉장히 찾기 힘든 버그가 생겨서 해결하는데 시간이 오래결렸다.
다음을 살펴보자
a = [1, 2, 3, [4, 5], 6]
b = a[:]
if a is not b: print('True')
if a[3] is b[3]: print('True')
a[3].append(6)
print(b)
True
True
[1, 2, 3, [4, 5, 6], 6]
a와 b의 id는 달라졌지만, 리스트 안의 리스트 즉 nested list는 얕은복사가 일어났음을 볼 수 있다.
Leave a comment