백준 12100번 2048(easy) (삼성 SW 역량 테스트 기출 문제)

사용한 알고리즘 : 브루트포스 (완전탐색)

꽤나 구현이 어려운... 문제였습니다.
우선 i,j의 값을 pair<숫자, 합쳐진여부(0,1로 구분)>로 받았습니다.
각 움직임에서 값들이 한번 합쳐지면, 이후에는 합쳐지지 않으므로, 이를 표현하기 위해
합쳐졌다면 second 값을 1, 안합쳐 졌다면 0으로 구분해 주었습니다.

이후 이를 info라는 struct로 만들어, 이 안에서 count 값(움직인 횟수)을 세어 주었습니다.
움직인 횟수는 최대 5번입니다.
처음 생각은 각 움직임을 visited 라는 bool 함수로 체크하면서 가려고 했으나,
움직임의 순서마다 각 배열값이 달라진다는걸 깨달아 그냥 움직인 횟수만 체크했습니다.
예를들어 오른쪽 - 왼쪽 - 위 - 아래 움직임과,
왼쪽-오른쪽-아래-위 움직임은 그 배열들이 다를 수 있습니다.

움직임은 1: 오른쪽, 2: 왼쪽, 3: 위, 4: 아래  총 4방향입니다.
각 방향마다 움직일때 시작 점을 주의했어야 했습니다.
예를 들어 오른쪽으로 이동할 때는,
각 row는 끝값부터 봤어야 합니다.

각 움직임을 행해줄 함수 (GoDirect라는 이름) 를 만들었습니다.
단순한 구현이었고, 약간... 까다롭습니다.
이 함수를 돌릴때 배열이 변화가 있는지 체크하여 (Move라는 bool로)
변화가 있으면 count++ 해주고 변화된 info를 출력해주었습니다.

브루트포스는 dfs 식으로 구현했습니다.
각 dfs 에서 구하고자 하는 답 (ans라는 이름) 을 최신화 해 주었으며,
count가 5를 넘으면 return 했습니다.
각 4방향 (1:오른쪽,2:왼쪽,3:위,4:아래)를 먼저 만들어놓은 움직임을 행해주는 함수에 돌리고, 배열들에 변화가 있다면 이를 다시 dfs로 넣어주는 식으로 dfs를 구현했습니다.

참고로 저는 배열이 예를들어 ' 0 0 0 4 ' 일때 왼쪽으로 움직이는 과정에서
' 4 0 0 0 ' 이 되어야 하는데 ' 0 0 4 0 ' 식으로 한번밖에 움직여주지 않는 오류를 범해서 이를 찾는데 상당한 시간을 썼습니다.. ㅠ

제 구현실력이 좋지 못해 피치못하게 코드 길이가 길어진 점에 대해 죄송하게 생각합니다...
풀고보니 굉장히 지저분한 코드가 됐습니다...