[백준] 12100번 2048(Easy)

문제 정의 

N*N의 보드에 주어진 숫자만을 통해서 2048 게임 방식을 따라 최대 5번 이동해서 만들 수 있는 가장 큰 블럭의 값을 구하는 프로그램을 구현하는 것이다.

문제 출처: 백준 온라인 저지(https://www.acmicpc.net/problem/12100)

문제 풀이

움직일 수 있는 방향은 상하좌우 총 4개이다. 최대 5번 이동해서 숫자를 크게 만들기 위해서는 4개의 방향에서 중복을 허용해서 순서를 가지는 5개의 방향을 고르는 모든 경우를 탐색하고, 만들어지는 최대 숫자를 출력한다. 총 4의5승의 경우가 나온다. 모든 경우에 밀어줘서 다 계산을 했는데 내가 고려하지 않은 부분이 너무 많았다. 처음에 짠 코드에서는 i와 i+1만 비교를 해서 옆에 있는 수와 같은지만 확인을 해버렸다. 8 0 0 8 인 경우 왼쪽으로 밀었을 때 16이 나와야 하는데 나는 숫자가 붙어있지 않아서 잘못되었었다. 그 부분을 고치고, 0인 부분을 다시 밀어주는 부분에서도 바로 옆에 0만 땡겨줘서 밀어준 쪽으로 다 합쳐지지 않았었다. 이런 고려사항들을 다 처리해주니 70%까지 채점이 되었다! 근데 그 이후에 바로 틀려버렸다. 또 다른 예외 테스트케이스를 고려못해준 것 같다.

20개 정도의 테스트케이스를 넣어봤는데 정답이 잘 나와서.. 새로운 방법으로 다시 풀어본다. deque를 이용해서 풀어보려고 한다. 이 문제에서는 0이 있으면 없애야하고, 밀어버린 방향으로 같은 숫자가 있으면 합쳐야하므로 그 때 이용해보려고 한다. 

아.. 완전히 새롭게 코드를 다시 다 짰는데 같은 퍼센트에서 틀렸습니다를 받았다. 충격적이었다. 근데 마침 떠오른게 나는 합쳐질 때만 항상 가장 큰 값이 될 줄 알고 그 때만 최대값을 갱신해줬는데 그래서 틀린거였다. 만약 input에서 가장 큰 값이 들어오고 다른게 합쳐져서 그 값보다 커지지 않는다면 그 input 값 자체가 최대값인데 그 부분을 생각하지 못했다. 이 부분을 고치니까 전에 짰던 코드랑 오늘 짰던 코드 둘다 맞았습니다였다. 너무한데 뿌듯하기도 하고..deque를 제대로 못써보긴 했지만 혹시나 필요한 경우에 생각이 날 것 같긴하다.

+ 추가

저번에 두 가지의 방법으로 풀고 오늘 또 다시 한번 풀어봤는데 3번 모두 구현한 방법이 각각 달라서 역시 구현하는 방법은 여러가지라는 것을 깨달았다. 아마 STL에 익숙하지 않았었거나, 아니면 떠올리지 못했어서 처음엔 이전의 값을 계속 임시적으로 저장해두고 배열을 돌면서 구현했었다. 그리고나서는 dequeue를 써봐야겠다는 생각이 들어서 썼었는데 저 때 왜 써봤더라..? 위에 풀이에서 생겼던 문제가 비슷하게 이번 구현에서도 있었는데 금방 발견해서 고쳤고, queue를 사용해서 4방향으로 미는 과정을 간단하게 했다. 첫 구현때는 vector 두번째는 dequeue, 세번째는 queue를 써서 구현했다. 한 문제를 여러가지 방법으로 풀어보고 각 풀이법을 보면서 복습하는 것도 좋은 방법인 것 같다.

코드

void slide(int cnt, int dir){ //오른쪽으로 밀기

int i, j;

int num;

int copy[21][21];

if(cnt == 5){ //다섯번 밀었음, 이부분에서 result 를 갱신해줘야하는데 중간과정에서 해줘서 틀렸다.

for(i=0; i<N; i++){

for(j=0; j<N; j++){

result = max(result, board[i][j]);

}

}

return ;

}

for(i=0; i<N; i++)

for(j=0; j<N; j++)

copy[i][j] = board[i][j];

if(dir == 0) //위쪽으로 밀기 i가 줄어들어야함

{

for(j=0; j<N; j++){

for(i=0; i<N; i++){

if(board[i][j] != 0){

dq.push_back(board[i][j]); //0빼고 넣음

}

}

if(dq.size() > 0)

{

num=0;

for(i=0; i < dq.size() ; i++)

{

if(i < dq.size()-1 && dq[i] == dq[i+1]){ //같아서 합친다면

board[num++][j] = dq[i]*2;

i++;

}

else

board[num++][j] = dq[i];

}

while(num < N){

board[num++][j] = 0;

}

dq.clear();

}

}

}

else if(dir == 1) //아래쪽으로 밀 때

{

for(j=0; j<N; j++){

for(i=N-1 ; i >= 0; i--){

if(board[i][j] != 0){

dq.push_back(board[i][j]); //0빼고 넣음

}

}

if(dq.size() > 0)

{

num=N-1;

for(i=0; i < dq.size() ; i++)

{

if(i < dq.size()-1 && dq[i] == dq[i+1]){ //같아서 합친다면

board[num--][j] = dq[i]*2;

i++;

}

else

board[num--][j] = dq[i];

}

while(num >= 0){

board[num--][j] = 0;

}

dq.clear();

}

}

}

else if(dir == 2) //왼쪽으로 밀 때

{

for(i=0; i<N; i++){

for(j=0 ; j < N; j++){

if(board[i][j] != 0){

dq.push_back(board[i][j]); //0빼고 넣음

}

}

if(dq.size() > 0)

{

num=0;

for(j=0; j < dq.size() ; j++)

{

if(j < dq.size()-1 && dq[j] == dq[j+1]){ //같아서 합친다면

board[i][num++] = dq[j]*2;

j++;

}

else

board[i][num++] = dq[j];

}

while(num < N){

board[i][num++] = 0;

}

dq.clear();

}

}

}

else //오른쪽으로 밀 때

{

for(i=0; i<N; i++){

for(j=N-1 ; j >= 0 ;j--){

if(board[i][j] != 0){

dq.push_back(board[i][j]); //0빼고 넣음

}

}

if(dq.size() > 0)

{

num=N-1;

for(j=0; j < dq.size() ; j++)

{

if(j < dq.size()-1 && dq[j] == dq[j+1]){ //같아서 합친다면

board[i][num--] = dq[j]*2;

j++;

}

else

board[i][num--] = dq[j];

}

while(num >= 0){

board[i][num--] = 0;

}

dq.clear();

}

}

}

slide(cnt+1, 0);

slide(cnt+1, 1);

slide(cnt+1, 2);

slide(cnt+1, 3);

for(i=0; i<N; i++)

{

for(j=0; j<N; j++)

board[i][j]=copy[i][j];

}

}