문제
2048 게임은 4×4 크기의 보드에서 혼자 즐기는 재미있는 게임이다. 이 링크를 누르면 게임을 해볼 수 있다.
이 게임에서 한 번의 이동은 보드 위에 있는 전체 블록을 상하좌우 네 방향 중 하나로 이동시키는 것이다. 이때, 같은 값을 갖는 두 블록이 충돌하면 두 블록은 하나로 합쳐지게 된다. 한 번의 이동에서 이미 합쳐진 블록은 또 다른 블록과 다시 합쳐질 수 없다. (실제 게임에서는 이동을 한 번 할 때마다 블록이 추가되지만, 이 문제에서 블록이 추가되는 경우는 없다)
(...)
마지막으로, 똑같은 수가 세 개가 있는 경우에는 이동하려고 하는 쪽의 칸이 먼저 합쳐진다. 예를 들어, 위로 이동시키는 경우에는 위쪽에 있는 블록이 먼저 합쳐지게 된다. <그림 14>의 경우에 위로 이동하면 <그림 15>를 만든다.
이 문제에서 다루는 2048 게임은 보드의 크기가 N×N 이다. 보드의 크기와 보드판의 블록 상태가 주어졌을 때, 최대 5번 이동해서 만들 수 있는 가장 큰 블록의 값을 구하는 프로그램을 작성하시오.
입력
첫째 줄에 보드의 크기 N (1 ≤ N ≤ 20)이 주어진다. 둘째 줄부터 N개의 줄에는 게임판의 초기 상태가 주어진다. 0은 빈 칸을 나타내며, 이외의 값은 모두 블록을 나타낸다. 블록에 쓰여 있는 수는 2보다 크거나 같고, 1024보다 작거나 같은 2의 제곱꼴이다. 블록은 적어도 하나 주어진다.
출력
최대 5번 이동시켜서 얻을 수 있는 가장 큰 블록을 출력한다.
내 풀이
다른 분의 풀이를 보고 풀었다. 최대한 코드를 이해하고 주석으로 달아놓으려 노력했다. 역시 다시 풀어볼 것!
up, down, left, right에 대해 행 또는 열의 모든 숫자를 queue에 push한 뒤 board는 0으로 초기화하고,
queue에 있는 요소들을 board에 추가해넣으면서 같은 숫자인 경우에는 더하는 식으로 다시 채워준다.
그리고 solve(cnt+1)함수를 부르는데, 이때 다른 방향에 대해서 돌 때는 solve에 처음 들어온 board로 돌아야 하기 때문에
원래 board를 deepcopy하여 저장해놓은 뒤 loop를 돌 때마다 다시 복원해준다.
다른 분의 풀이에서는 [:]를 사용하여 복원해주었는데, 어떤 것을 사용하든 상관은 없지만 내가 한 것처럼 deepcopy를 사용할 경우에는 반드시 import copy를 해줘야 한다.
cnt가 5가 되면 (5번 이동했으면) ans(기존에 저장되어 있던 max값)을 업데이트해준다.
모든 경우의 수에 대하여 다 확인했다면(solve함수가 더 이상 돌지 않는다면) print(ans)
시간복잡도는 O(N**2*4**5)가 된다.
cf) deepcopy와 swallowcopy
list는 mutable하기 때문에 deepcopy가 필요한데, 만약 이 list가 [1,2,3]과 같이 한 개의 차원으로 구성되어 있다면 swallowcopy로도 충분하다. a = [1,2,3]일 때 b = a[:]와 같은 방식이 swallowcopy이다. 그러나 만약 a=[[1],[2],[3]]과 같이 mutable 내에 또다서 mutable이 있는 식의 형태를 띄고 있을 때 b = a[:] (swallow copy) 같은 식이라면 a[0][0] = 1 이런 식으로 수정할 경우 b에도 똑같이 반영된다. 이런 상황을 막고 싶을 때 deepcopy가 필요하다. python에서는 copy 라이브러리에서 deepcopy를 지원해주기 때문에 import copy 혹은 from copy import deepcopy를 써 주고 b = copy.deepcopy(a)라고 쓰는 것만으로 해결 가능하다.
