[BOJ] 백준 12100번: 2048(Easy)

2048(Easy)

문제

게임의 규칙이 문제의 설명과 같을 때 최대 5번 움직여서 만들수 있는 최대 블록의 값을 구하는 문제이다.

문제 풀이

1. 깊이가 최대 5이고 하나의 상태공간에서 상하좌우 4개의 상태공간으로 전이 가능하다. 

    다음 상태공간을 만드는데 \(O(N^2)\)이 걸리므로, \(O(N^2 4^5)\) 로 해결 가능하다.

2. 각 행(또는 열)에 대해 0이 아닌 블록들을 모은 후 2개씩 묶어서 합치는게 가능하면 합친다. 

    결과를 다시 해당 열에 복사한다.

3. 구현 팁으로는 상, 하 // 좌, 우는 각각 순서만 반대로 넣으면 되고 세로와 가로는 행과 열만 바꾸어 넣으면 된다.

** 구현 실수하기 쉬운 예를 적어 보겠다.

- 상, 하, 좌, 우를 따로 구현 하였는데 규칙이 다르게 구현 되어있음.

- 2 0 2 같이 중간에 0이 끼인 경우를 생각하지 않음.

- dfs 한 후에 다시 복귀할 때 원래 상태로 되돌리지 않음.

- max값을 찾는 시점이 잘못됨. ( 최종 depth가 5일 때 찾아야함 )

- (2 2 4) -> (4 4) 와 같이 이미 결합된 블럭은 한 턴에 다시 결합 하지 않는 규칙을 고려하지 않음

 

소스 코드