백준 12100. 2048 (Easy)

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

12100번: 2048 (Easy)

 

문제를 읽고 재귀를 이용한 dfs로 풀고자 했는데 도대체 탈출 조건을 어떤 식으로 구성할지 고민하다가 최대 5번 이동시켜서 얻을수 있는 가장 큰 블록을 출력하라는 조건을 읽고 바로 풀렸다 .. 문제를 꼼꼼히 읽자 .. 

 

우선 블록들을 특정 방향으로 움직이는 기능을 구현해야 한다.

이건 그냥 4방향 개별적으로 구현해 줬다. 

위 방향이라면 0을 제외한 숫자들을 위로 밀어주고, 붙어있는 블록 중 같은 숫자가 있다면 한개를 2배 한개는 0으로 만들어 준후에 다시 한번 밀어주면 된다.

어떻게 잘 구현하면 4방향을 하나의 함수로도 만들수 있을것 같긴한데... 

 

가장 큰 블록을 구하는것은 재귀 dfs를 이용해 순열을 만들듯이 구현해줬다.

4방향 중 하나의 방향으로 이동시키기 전에 현재 보드를 기억해놨다가 특정 방향으로 이동시킨후 되돌아 왔을때 복구시켜주면 된다.

재귀의 탈출 조건은 깊이가 5가 되면 리턴해주도록 했다.