[C++][백준 12100] 2048(Easy)

문제설명은 더보기를 눌러주세요

문제

문제 링크 : www.acmicpc.net/problem/12100

2048 게임은 4×4 크기의 보드에서 혼자 즐기는 재미있는 게임이다. 

이 게임에서 한 번의 이동은 보드 위에 있는 전체 블록을 상하좌우 네 방향 중 하나로 이동시키는 것이다. 이때, 같은 값을 갖는 두 블록이 충돌하면 두 블록은 하나로 합쳐지게 된다. 한 번의 이동에서 이미 합쳐진 블록은 또 다른 블록과 다시 합쳐질 수 없다. (실제 게임에서는 이동을 한 번 할 때마다 블록이 추가되지만, 이 문제에서 블록이 추가되는 경우는 없다)

<그림 1>의 경우에서 위로 블록을 이동시키면 <그림 2>의 상태가 된다. 여기서, 왼쪽으로 블록을 이동시키면 <그림 3>의 상태가 된다.

<그림 4>의 상태에서 블록을 오른쪽으로 이동시키면 <그림 5>가 되고, 여기서 다시 위로 블록을 이동시키면 <그림 6>이 된다. 여기서 오른쪽으로 블록을 이동시켜 <그림 7>을 만들 수 있다.

<그림 8>의 상태에서 왼쪽으로 블록을 옮기면 어떻게 될까? 2가 충돌하기 때문에, 4로 합쳐지게 되고 <그림 9>의 상태가 된다.

<그림 12>의 경우에 위로 블록을 이동시키면 <그림 13>의 상태가 되는데, 그 이유는 한 번의 이동에서 이미 합쳐진 블록은 또 합쳐질 수 없기 때문이다.

마지막으로, 똑같은 수가 세 개가 있는 경우에는 이동하려고 하는 쪽의 칸이 먼저 합쳐진다. 예를 들어, 위로 이동시키는 경우에는 위쪽에 있는 블록이 먼저 합쳐지게 된다. <그림 14>의 경우에 위로 이동하면 <그림 15>를 만든다.

이 문제에서 다루는 2048 게임은 보드의 크기가 N×N 이다. 보드의 크기와 보드판의 블록 상태가 주어졌을 때, 최대 5번 이동해서 만들 수 있는 가장 큰 블록의 값을 구하는 프로그램을 작성하시오.

입력

첫째 줄에 보드의 크기 N (1 ≤ N ≤ 20)이 주어진다. 둘째 줄부터 N개의 줄에는 게임판의 초기 상태가 주어진다. 0은 빈 칸을 나타내며, 이외의 값은 모두 블록을 나타낸다. 블록에 쓰여 있는 수는 2보다 크거나 같고, 1024보다 작거나 같은 2의 제곱꼴이다. 블록은 적어도 하나 주어진다.

출력

최대 5번 이동시켜서 얻을 수 있는 가장 큰 블록을 출력한다.

 

-풀이-

1. 저는 해당문제를 중복순열을 이용해서 풀었습니다.
   길이 5인 배열에 00000, 00001, 00002, 00003, 00004 / 00010, 00011, 00012, 00013, 00014, 00020 ...
   0은 동, 1은 서, 2는 남, 3은 북쪽으로 미는 것을 의미합니다. 

2. 길이 5인 배열이 완성되면 배열에 저장된 대로 밀기만 하면 됩니다. 

3. 미는 과정에서는 vector를 이용했습니다. 예를 들어, 한 줄에 블록이 [2 0 4 4 0]과 같이 존재한다면 
   벡터에 2 4 4 를 담아두고 (0은 제외합니다) 맵의 해당 줄을 초기화 시켜줍니다.
   처음부터 끝까지 벡터를 돌며 현재값과 바로 다음값이 같다면, 합쳐지는 경우이므로 합쳐서 맵에 넣어줍니다.
   현재값과 다음값이 다르다면 합쳐지지 않으므로 현재값만 맵에 넣어줍니다.

4. 아마 서쪽으로 미는 경우가 가장 이해하시기 쉬울것입니다. 주석을 통해 더 자세히 아실 수 있습니다.
    나머지 동, 남, 북쪽으로 미는 경우도 같은 방식으로 진행해주시면 됩니다. 

 

-코드-

#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;
void move(int type);
void DFS(int cnt);
int map[21][21], tempMap[21][21];
int turn[5];
int N, res=0;
int main(){
    cin >> N;
    for(int i=1; i<=N; i++){
        for(int j=1; j<=N; j++){
            cin >> tempMap[i][j];
        }
    }
    DFS(0);
    cout << res;
}

void DFS(int cnt) {
    if(cnt == 5) {
        for(int i=1; i<=N; i++) { // map 카피하는 과정
            for(int j=1; j<=N; j++){
                map[i][j] = tempMap[i][j];
            }
        }
        
        for(int i=0; i<5; i++) move(turn[i]); // 만들었던 중복순열대로 move시킨다.
        
        for(int i=1; i<=N; i++){ // 최댓값을 구하는 과정
            for(int j=1; j<=N; j++){
                if(res < map[i][j]) res = map[i][j];
            }
        }
        return;
    }
    for(int i=0; i<5; i++){
        turn[cnt] = i; // 중복 순열 만들기
        DFS(cnt+1);
    }
}

void move(int type){ // type : 0 1 2 3 (동 서 남 북)
    vector<int> v; 
    if(type == 0) {
        for(int i=1; i<=N; i++){
            for(int j=N; j>=1; j--) {
                if(map[i][j]) v.push_back(map[i][j]); 
                map[i][j] = 0; 
            }
            for(int j=0, idx=N; j<v.size(); j++) { 
                if(v[j] == v[j+1] && j+1 < v.size()) map[i][idx] = v[j++]*2; 
                else map[i][idx] = v[j]; 
                idx--; 
            }
            v.clear(); 
        }
    } else if(type == 1) {
        for(int i=1; i<=N; i++){
            for(int j=1; j<=N; j++) {
                if(map[i][j]) v.push_back(map[i][j]); // 처음부터 돌면서 벡터에 일단 다 넣어준다.
                map[i][j] = 0; // 넣어주면서 맵은 초기화
            }
            for(int j=0, idx=1; j<v.size(); j++) { // 벡터를 처음부터 끝까지 돌면서
                if(v[j] == v[j+1] && j+1 < v.size()) map[i][idx] = v[j++]*2; // 만약 벡터의 현재값과 다음값이 같으면 합칠 수 있으니 2배 해준 값을 넣어준다. 이 경우엔 한번 더 j++를 해줘야한다.
                else map[i][idx] = v[j]; // 다르다면 그냥 현재 벡터값을 맵에 넣어준다.
                idx++; 
            }
            v.clear();
        }
    } else if(type == 2) {
        for(int i=1; i<=N; i++){
            for(int j=N; j>=1; j--) {
                if(map[j][i]) v.push_back(map[j][i]);
                map[j][i] = 0;
            }
            for(int j=0, idx=N; j<v.size(); j++) {
                if(v[j] == v[j+1] && j+1 < v.size()) map[idx][i] = v[j++]*2;
                else map[idx][i] = v[j];
                idx--;
            }
            v.clear();
        }
    } else {
        for(int i=1; i<=N; i++){
            for(int j=1; j<=N; j++) {
                if(map[j][i]) v.push_back(map[j][i]);
                map[j][i] = 0;
            }
            for(int j=0, idx=1; j<v.size(); j++) {
                if(v[j] == v[j+1] && j+1 < v.size()) map[idx][i] = v[j++]*2;
                else map[idx][i] = v[j];
                idx++;
            }
            v.clear();
        }
    }
}