[백준]2048(easy)

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

12100번: 2048 (Easy)

적당히 1시간 30분정도 걸린거같다. 

dfs + 시뮬레이션의 문제인거 같고 구슬탈출과 좀 유사한 면이 있는것 같다.

다른점은 이 문제의 경우는 맵을 수정하는것이고 구슬탈출은 맵을 놔두고 구슬만 움직여준다는 것이다.

그리고 이 문제는 5번이라는 숫자가 정해져있었다.

먼저, dfs를 진행할때, 배열을 파라미터로 넘겨주면 정보가 바뀌어 그런식으로는 코딩을 할 수없고, 백업배열을

만들어서 작업을 진행해 주어야한다. dfs완전탐색 문제를 해결할 때, 백업을 만들지 파라미터로 전해줄지

잘 생각해봐야 할것같다.

이 문제의 경우 상하좌우로 움직일 수 있는것을 순열로 나타낸 다음 그 순열들에 대해 차례로 시뮬레이션을

실행해 주었다. 

이 문제의 시뮬레이션적인 부분은 Queue를 이용하여 해결하였다.

여러가지 구현방법이 있겠지만, 생각났던 아이디어는 2가지였다.

1. 한 벽돌씩 밀어넣으면서 숫자를 업데이트 하는것

2.모든 벽돌을 밀어넣은 다음 합칠 수 있는것만 합치는것.

둘다 어찌 됐든, Queue에 push, pop하는 과정이 편리하기때문에 queue에 넣고 하나씩 빼면서 합칠것들은 합치는 

식으로 코딩을 해야겠다고 생각했다.

한 방향에 대해서만 구현하면 나머지는 조금만 수정해주면 된다.

 

#include <iostream>
#include <cstring>
#include <vector>
#include <queue>
using namespace std;
 
/*#map을 인자로 넘길수가 없다 정보가 변한다 즉 copymap이 필요하다#
#구슬탈출과 다른점은 이 문제는 맵자체가 변한다는 것#
 
1.dfs로 5번에 대해서 방향들을 순열로 구성
2.길이가 len이 되면 copy맵에 원래 맵을 복사하고 프로세스 진행 후, 최대값 구함.
 
4.시뮬은 queue를 이용해서 합치고 맵에 매핑해서 구해보자(0)
예외(다양한 손시뮬상황에서 전부생각할것!!)::방향자체가 다 가능해서 괜츈할듯*/
 
int N;
vector<int> v1;
queue<int> q1; //한줄의 벽돌들을 관리
int map[21][21];
int c_map[21][21];
int ans = -1e9;
 
//상하좌우 (0,1,2,3) 순으로 구현
void UP() {
    for (int c = 0; c < N; c++) {
        //모든 행마다
        
        for (int r = 0; r < N; r++) {//위에서 아래로 블록입력
            if (c_map[r][c] != 0) { q1.push(c_map[r][c]); c_map[r][c] = 0; }
        }
 
        //queue에서 빼면서 합쳐주기
        if (q1.empty()) continue; //queue에 아무것도 없는데 빼서 문제가 됐던거임...
        c_map[0][c] = q1.front(); //첫번째꺼는 바로 넣기
        q1.pop(); 
 
        int cnt = 1; //어디까지 채워져있나 카운트
        bool aa = false; //전블록이 합쳐진것인지의 여부
        while (!q1.empty()) {
            int nn = q1.front();
            q1.pop();
 
            if (aa == false && nn == c_map[cnt-1][c]) {
                //합친적이 없는데 값이 같은경우
                aa = true; //합친다
                c_map[cnt-1][c] += nn; //값을 더한다
            }
            else {
                //합친적이 있거나 값이 다른경우
                aa = false; //안합친다
                c_map[cnt][c] = nn; //입력
                cnt++;
            }
        }//end while
    }
}
 
void DOWN() {
    for (int c = 0; c < N; c++) {
        //모든 행마다
 
        for (int r = N-1; r >=0 ; r--) {//아래에서 위 블록입력
            if (c_map[r][c] != 0) { q1.push(c_map[r][c]); c_map[r][c] = 0; }
        }
 
        //queue에서 빼면서 합쳐주기
        if (q1.empty()) continue; //queue에 아무것도 없는데 빼서 문제가 됐던거임...
        c_map[N-1][c] = q1.front(); //첫번째꺼는 바로 넣기
        q1.pop();
 
        int cnt = N-2; //어디까지 채워져있나 카운트
        bool aa = false; //전블록이 합쳐진것인지의 여부
        while (!q1.empty()) {
            int nn = q1.front();
            q1.pop();
 
            if (aa == false && nn == c_map[cnt + 1][c]) {
                //합친적이 없는데 값이 같은경우
                aa = true; //합친다
                c_map[cnt + 1][c] += nn; //값을 더한다
            }
            else {
                //합친적이 있거나 값이 다른경우
                aa = false; //안합친다
                c_map[cnt][c] = nn; //입력
                cnt--;
            }
        }//end while
    }
}
 
void LEFT() {
    for (int r = 0; r < N; r++) {
        //모든 열마다
 
        for (int c = 0; c < N ; c++) {//왼에서 오 블록입력
            if (c_map[r][c] != 0) { q1.push(c_map[r][c]); c_map[r][c] = 0; }
        }
 
        //queue에서 빼면서 합쳐주기
        if (q1.empty()) continue; //queue에 아무것도 없는데 빼서 문제가 됐던거임...
        c_map[r][0] = q1.front(); //첫번째꺼는 바로 넣기
        q1.pop();
 
        int cnt = 1; //어디까지 채워져있나 카운트
        bool aa = false; //전블록이 합쳐진것인지의 여부
        while (!q1.empty()) {
            int nn = q1.front();
            q1.pop();
 
            if (aa == false && nn == c_map[r][cnt - 1]) {
                //합친적이 없는데 값이 같은경우
                aa = true; //합친다
                c_map[r][cnt - 1] += nn; //값을 더한다
            }
            else {
                //합친적이 있거나 값이 다른경우
                aa = false; //안합친다
                c_map[r][cnt] = nn; //입력
                cnt++;
            }
        }//end while
    }
}
 
void RIGHT() {
    for (int r = 0; r < N; r++) {
        //모든 열마다
 
        for (int c = N-1; c >= 0; c--) {//오 -> 왼 블록입력
            if (c_map[r][c] != 0) { q1.push(c_map[r][c]); c_map[r][c] = 0; }
        }
 
        //queue에서 빼면서 합쳐주기
        if (q1.empty()) continue; //queue에 아무것도 없는데 빼서 문제가 됐던거임...
        c_map[r][N-1] = q1.front(); //첫번째꺼는 바로 넣기
        q1.pop();
 
        int cnt = N-2; //어디까지 채워져있나 카운트
        bool aa = false; //전블록이 합쳐진것인지의 여부
        while (!q1.empty()) {
            int nn = q1.front();
            q1.pop();
 
            if (aa == false && nn == c_map[r][cnt + 1]) {
                //합친적이 없는데 값이 같은경우
                aa = true; //합친다
                c_map[r][cnt + 1] += nn; //값을 더한다
            }
            else {
                //합친적이 있거나 값이 다른경우
                aa = false; //안합친다
                c_map[r][cnt] = nn; //입력
                cnt--;
            }
        }//end while
    }
}
 
void dfs(int len) {
    if (len == 5) {
        //c_map으로 작업(기존의 정보는 바뀌지않게하기위해)
        memcpy(c_map, map, sizeof(c_map));
 
        for (int i = 0; i < 5; i++) {
            if (v1[i] == 1) UP();
            else if (v1[i] == 2) DOWN();
            else if (v1[i] == 3) LEFT();
            else if (v1[i] == 4) RIGHT();        
        }
 
        for (int i = 0; i < N; i++) {
            for (int j = 0; j < N; j++) {
                if (c_map[i][j] >= ans) ans = c_map[i][j];
            }
        }
        
        return; 
    }
 
    for (int i = 1; i < 5; i++) { //1~4까지의 숫자로 순열만들기
        v1.push_back(i);
        dfs(len + 1);
        v1.pop_back();
    }
}
 
int main()
{    
    cin >> N;
    for (int i = 0; i < N; i++) for (int j = 0; j < N; j++) cin >> map[i][j];
 
    dfs(0);
    printf("%d\n", ans);
 
    return 0;
}