[DFS] 12100번 2048 (Easy)

12100_2048 (Easy)

12100번 2048 (Easy)

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

문제

2048 게임은 4×4 크기의 보드에서 혼자 즐기는 재미있는 게임이다. 이 링크를 누르면 게임을 해볼 수 있다.

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

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

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

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

<그림 10>에서 위로 블록을 이동시키면 <그림 11>의 상태가 된다.

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

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

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

입력

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

출력

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

예제 입력

예제 출력

해결방법

DFS 를 통해 모든 경우를 다해보는 완전탐색 문제이다
시간복잡도만 계산한다면 탐색은 어렵지 않지만 구현이 어려운 편에 속하는 문제였다

⭐️ 솔루션 ⭐️

보드를 기울여 값을 이동시키고 합치는 구현 부분이 ㄹㅇ 너무 어려웠다...
또한 방문 처리에 대한 확신이 없어서 때려맞추듯 구현하였다...
기본 로직은 설계를 하였으나 섬세한 부분에서 자꾸 미스가 났다

전체적인 문제 흐름은 다음과 같다

현재 맵을 인자로 DFS 탐색을 시작한다
상 하 좌 우 4가지 방향으로 보드를 기울이며 탐색을 수행한다
만약 보드를 기울인 횟수가 5번을 넘으면 return 해준다
또한 모든 탐색 수행마다 보드의 현재 최대값을 구하여 갱신해준다

[ 보드를 기울이는 구현 부분 ]

사실 이 부분이 이 문제의 핵심이라고 생각한다
처음에는 아래와 같은 로직을 생각했다

보드를 해당 방향으로 기울인다

같은 값을 가지고 있는 노드끼리 합친다

다시 보드를 기울인다

하지만 이러한 로직은 막상 구현하려니 너무 하드코딩이었고 예외의 경우가 많을거같은 느낌이들었다

결국 구글링을 통해 약간의 솔루션을 얻었다
방법은 큐를 사용하는 것이었다 !!

먼저 기울이는 방향부터 반대 방향까지 노드 중, 값을 가지고 있는 노드의 값을 큐에 넣는다

다시 기울이는 방향의 끝 노드 부터, 큐에서 값을 pop 하여 채워준다

만약 노드가 빈칸이라면 그대로 값을 넣는다

만약 빈칸이 아니고 큐에서 꺼낸값과 일치한다면 수를 합친 뒤, 인덱스를 증가 또는 감소시킨다

만약 빈칸이 아니고 큐에서 꺼낸값과 다르다면 인덱스를 증가 또는 감소시킨 뒤, 값을 넣어준다

[ 시간복잡도 ]

일단 하나의 상태에서 움직일 수 있는 방법은 상 하 좌 우 4가지 방법이다
또한 최대 움직일 수 있는 횟수는 5이므로 모든 경우의 시간은 4^5 가 발생한다
각 움직임마다 모든 보드의 상태는 변할 수 있다
따라서 4방향 모두 각각 n^2 의 시간이 발생한다
결국 전체 시간복잡도는 1024 * n^2 * 4 이다
이 문제는 O(n^2 * 4 * 1024) 의 시간복잡도를 가진다

소스코드

문제 해결 시간 : 2h 20m
메모리 : 2124 KB
시간 : 24 ms

#include <iostream>
#include <stdio.h>
#include <math.h>
#include <cstring>
#include <queue>
#include <vector>
#include <algorithm>
#define MAX 21
#define RIGHT 0
#define LEFT 1
#define DOWN 2
#define UP 3

using namespace std;

int n,ans;
vector<vector<int>> map(MAX,vector<int>(MAX));
queue<int> q;

/*
 
 보드를 기울이는 함수이다
 각 방향별로 인덱스가 다르기 때문에 switch문으로 분기시켜야한다
 
 1. 먼저 기울이는 방향부터 반대방향까지 값을 모두 큐에 넣는다
 2. 기울이는 방향의 끝칸부터 큐에서 pop하여 값을 채운다
    - 만약 빈칸이라면 그대로 값을 채운다
    - 만약 빈칸이 아니고 큐에서 꺼낸값과 일치하다면 수를 합친 뒤, 인덱스를 증가 또는 감소시킨다
    - 만약 빈칸이 아닌고 큐에서 꺼낸값과 다르다면 인덱스를 증가 또는 감소시킨 뒤, 값을 넣어준다
 
*/

vector<vector<int>> move_board(vector<vector<int>> v,int dir){
    switch (dir) {
        case RIGHT:
        {
            // 행
            for(int i=0; i<n; i++){
                // 열
                for(int j=n-1; j>=0; j--){
                    if(v[i][j] != 0){
                        q.push(v[i][j]);
                        v[i][j] = 0;
                    }
                }
                
                // 다시 채워넣기!
                int j = n-1;
                while(!q.empty()){
                    int num = q.front();
                    q.pop();
                    
                    if(v[i][j] == 0){
                        v[i][j] = num;
                    }else{
                        if(num == v[i][j]){
                            v[i][j] *= 2;
                            j--;
                        }
                        else{
                            j--;
                            v[i][j] = num;
                        }
                    }
                }
            }
            break;
        }
        case LEFT:
        {
            // 행
            for(int i=0; i<n; i++){
                // 열
                for(int j=0; j<n; j++){
                    if(v[i][j] != 0){
                        q.push(v[i][j]);
                        v[i][j] = 0;
                    }
                }
                
                // 다시 채워넣기!
                int j = 0;
                while(!q.empty()){
                    int num = q.front();
                    q.pop();
                    
                    if(v[i][j] == 0){
                        v[i][j] = num;
                    }else{
                        if(num == v[i][j]){
                            v[i][j] *= 2;
                            j++;
                        }else{
                            j++;
                            v[i][j] = num;
                        }
                    }
                }
            }
            break;
        }
        case DOWN:
        {
            // 열
            for(int j=0; j<n; j++){
                // 행
                for(int i=n-1; i>=0; i--){
                    if(v[i][j] != 0){
                        q.push(v[i][j]);
                        v[i][j] = 0;
                    }
                }
                
                // 다시 채워넣기!
                int i = n-1;
                while(!q.empty()){
                    int num = q.front();
                    q.pop();
                    
                    if(v[i][j] == 0){
                        v[i][j] = num;
                    }else{
                        if(num == v[i][j]){
                            v[i][j] *= 2;
                            i--;
                        }else{
                            i--;
                            v[i][j] = num;
                        }
                    }
                }
            }
            break;
        }
        case UP:
        {
            // 열
            for(int j=0; j<n; j++){
                // 행
                for(int i=0; i<n; i++){
                    if(v[i][j] != 0){
                        q.push(v[i][j]);
                        v[i][j] = 0;
                    }
                }
                
                // 다시 채워넣기!
                int i = 0;
                while(!q.empty()){
                    int num = q.front();
                    q.pop();
                    
                    if(v[i][j] == 0){
                        v[i][j] = num;
                    }else{
                        if(num == v[i][j]){
                            v[i][j] *= 2;
                            i++;
                        }else{
                            i++;
                            v[i][j] = num;
                        }
                    }
                }
            }
            break;
        }
            
        default:
            break;
    }
    
    return v;
}

// 보드에서 가장 큰값을 리턴하는 함수
int getMaxValue(vector<vector<int>> v){
    int res = 0;
    for(int i=0; i<n; i++){
        for(int j=0; j<n; j++){
            res = max(res,v[i][j]);
        }
    }
    return res;
}

void dfs(vector<vector<int>> v,int cnt){
    // 횟수를 초과한 경우
    if(cnt > 5) return;
    
    // 현재의 vector에서 최대값을 구함
    ans = max(ans,getMaxValue(v));
    
    // 4 방향 탐색
    for(int i=0; i<4; i++){
        vector<vector<int>> nv = move_board(v,i);
        dfs(nv,cnt+1);
    }
}

int main(int argc, const char * argv[]) {
    // cin,cout 속도향상
    ios_base::sync_with_stdio(false);
    cin.tie(NULL); cout.tie(NULL);
    
    cin >> n;
    for(int i=0; i<n; i++){
        for(int j=0; j<n; j++){
            cin >> map[i][j];
        }
    }
    
    ans = 0;
    dfs(map,0);
    cout << ans << "\n";
    
    return 0;
}

저작자표시

'Algorithm > BOJ 문제풀이' 카테고리의 다른 글

[DFS] 3019번 테트리스 (0)	2019.01.17
[DFS] 14500번 테트로미노 (0)	2019.01.16
[BFS] 15653번 구슬 탈출 4 (0)	2019.01.15
[DFS] 13460번 구슬 탈출 2 (0)	2019.01.15
[DFS] 15684번 사다리 조작 (0)	2019.01.14

SuperM