백준 12100번 2048(Easy) -Java

문제 링크 - > www.acmicpc.net/problem/12100

12100번: 2048 (Easy)

문제 분석 : 

각 블록들은 상, 하, 좌, 우 네 방향 중 한 방향으로 모두 이동하게 된다.

이 때, 같은 값을 가지는 두 블록이 충돌한다면 두 블록이 하나로 합쳐지게 되는데 

한번의 이동에서 합쳐진 블록은 다음 이동까지 합쳐질 수 없는 조건에서 

최대 5번까지의 이동 중 나올 수 있는 가장 큰 값을 구해야 하는 문제이다.

상 -> (상, 하, 좌, 우) -> (상, 하, 좌, 우) -> .... 로 이동하며 모든 경우의 수를 찾아야 하기에 재귀적으로 접근한다.

 

문제 접근 : 

1. 각 4 방향 (상, 하, 좌, 우)의 방향으로 이동시킨다.

   - 이동 할 때 문제의 조건인 한 번의 이동에서 이미 합쳐진 블록은 또 다른 블록과 다시 합쳐질 수 없다.는 조건을

     만족하기 위해 boolean 이차원 배열 visit[][]을 선언해 처리해 주었다.

 

2. 1번에서 이동한 블록 배열들을 가지고 이동 횟수가 5번이 될 때까지 다시 1번으로 돌아간다.

   - 한번의 이동을 하면 4가지의 선택지가 있으므로 4가지 모두 탐색할 수 있도록 재귀적으로 구현해야 하며

     핵심은 블록 배열의 복사와 원상복구다.

 

3. 이동 횟수가 5번 즉, 문제 조건에 충족된다면 중단하고 Maximum 값을 찾아내 리턴한다.

 

소스 코드 :

github.com/Kim-SiHwan/Algorithm/blob/main/BOJ/12100.java