[BOJ] 12100 2048 (Easy) (C/C++)

https://www.acmicpc.net/problem/12100

12100번: 2048 (Easy)

문제

2048 게임은 4×4 크기의 보드에서 혼자 즐기는 재미있는 게임이다. 이 링크를 누르면 게임을 해볼 수 있다.

이 게임에서 한 번의 이동은 보드 위에 있는 전체 블록을 상하좌우 네 방향 중 하나로 이동시키는 것이다. 이때, 같은 값을 갖는 두 블록이 충돌하면 두 블록은 하나로 합쳐지게 된다. 한 번의 이동에서 이미 합쳐진 블록은 또 다른 블록과 다시 합쳐질 수 없다. (실제 게임에서는 이동을 한 번 할 때마다 블록이 추가되지만, 이 문제에서 블록이 추가되는 경우는 없다)

 

이 문제에서 다루는 2048 게임은 보드의 크기가 N×N 이다. 보드의 크기와 보드판의 블록 상태가 주어졌을 때, 최대 5번 이동해서 만들 수 있는 가장 큰 블록의 값을 구하는 프로그램을 작성하시오.

입력

첫째 줄에 보드의 크기 N (1 ≤ N ≤ 20)이 주어진다. 둘째 줄부터 N개의 줄에는 게임판의 초기 상태가 주어진다. 0은 빈 칸을 나타내며, 이외의 값은 모두 블록을 나타낸다. 블록에 쓰여 있는 수는 2보다 크거나 같고, 1024보다 작거나 같은 2의 제곱꼴이다. 블록은 적어도 하나 주어진다.

출력

최대 5번 이동시켜서 얻을 수 있는 가장 큰 블록을 출력한다.

---

어제에 이은 구현 문제. 문제를 어떻게 풀어야겠다는 생각은 쉽게 들었지만, 그 중간 과정 중에 하나인 보드를 움직이는 함수를 짜는데 시간이 많이 들었다.

 

어차피 N은 20, 이동 횟수가 최대 5번이기 때문에 완전 탐색으로 해도 무방하겠다는 생각이 들었다. BFS보단 DFS가 구현하기 더 쉬울 것 같아서 DFS로 완전 탐색을 하기로 했다. 처음엔 현재 보드 상태에서 상하좌우 네 방향 중 어떤 한 방향으로 이동한 다음에 DFS 함수를 한번 더 호출하는 형태로 생각했다. 그랬더니 각 네 방향으로 이동하는 함수를 각각 구현하게 생긴 것이었다. 어떻게 심플하게 구현할 방법이 없을까 고민해봤는데 쉽게 떠오르지 않았다.

 

그래서 다른 사람들도 과연 이렇게 무지막지하게 구현했을까해서 인터넷을 뒤져보게 됐다. 거의 모든 사람이 상하좌우 함수를 따로 구현하고 있었다. 갑자기 예전에 아는 사람이 이 문제를 풀었던 것이 생각나 그 사람은 어떻게 풀었나 보러 갔는데 그 사람은 보드 이동을 한 방향으로만 하고 있었다. 그다음에 보드 자체를 회전시킴으로써 네 방향을 모두 구현했다. 그래서 나도 그런 방향으로 구현해봤다. 

 

rotateBoard 함수는 보드를 시계방향으로 90도 시키는 함수이고, moveBoard 함수는 보드를 왼쪽으로 미는 함수다. 따라서 좌 하 우 상 순으로 보드를 움직이게 된다.

 

 

후기)

역시 세상에 안되는 건 없다. 그냥 내가 할 줄 모르는 것뿐이다.