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

문제

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

12100번: 2048 (Easy)

[참고 링크 1] [참고 링크 2 : 구데타마 님의 '꾸준함' 블로그]

 

풀이 과정

1. 문제의 조건에 맞도록 각 방향에 맞게 블록들을 이동하는 함수를 구현한다.

    이때 '한 번의 이동에서 이미 합쳐진 블록은 또 다른 블록과 다시 합쳐질 수 없다.'라는 조건에 주의해야 한다.

2. 1번에서 구현한 이동 함수를 5번 수행한 모든 경우를 탐색해야 한다.

3. DFS 알고리즘을 적용하여 탐색하며, 5번의 이동이 끝난 경우의 각 블록의 크기를 비교하여 가장 큰 값들을 기록한다.

4. 최종적으로 기록되어있는 가장 큰 값을 출력한다.

 

 

세부 풀이

이동 함수를 구현하는 데 있어서 언급된 문제의 조건을 잘 적용해야 한다. 

예를 들어 2 2 4 16 인 경우를 왼쪽으로 이동시킨 경우 4 4 16 0 이 되어야 한다. (8 16 0 0 이 되면 안 된다.)

첫 제출 때 해당 조건을 만족하지 않아 오답으로 채점되었었다.

 

이를 해결하기 위한 방법으로 이동하는 방향을 각각 쪼갠 뒤, 한 줄 한 줄을 queue에 담아 처리하는 방식을 이용했다.

위의 그림에서처럼 이동하는 방향의 진행을 각 행/열 로 쪼개어 수행하도록 구현했다.

 

소스코드 이해에 도움이 되었으면 해서 적어본 자세한 코드의 동작 과정을 예시를 들어 설명한 부분입니다.

첫 번째 그림 예시와 같은 경우에서 이동 함수가 수행되면
column 0에 있는 0 0 2 0을 탐색하며 queue에 2를 넣게 된다. 이때 column 0 은 0 0 0 0으로 초기화한다.
이때의 index는 위에서부터 채워져야 하기 때문에 0으로 설정하여 탐색을 시작한다.

index = 0 
보드[index][0] = 0 이므로 queue에 있던 제일 앞의 값을 보드[index][0] 위치에 저장한다.
다음 queue의 값을 탐색하기 전까지 index를 증가시키지 않는다.
다음 queue에 있는 값이 같은 값이면, 같은 칸에 덧셈을 진행해야 하기 때문이다.
최종적으로 column 1은  두 번째 그림과 같이 2 0 2 0 이 된다.


두 번째 그림에서 이동 함수가 수행되면
row 1에 있는 2 0 2 0을 탐색하여 queue에 2 2를 넣게 된다. 이때 row 1 은 0 0 0 0으로 초기화한다.
이때 index는 왼쪽에서부터 채워져야 하기 때문에 0으로 설정하여 탐색을 시작한다.

index = 0
보드[0][index] = 0이다. (초기화된 상황에 의해) 따라서 보드[0][index]=2를 수행한다.
index를 증가시키지 않는다.
다음 queue의 값을 탐색한다.
현재 index : 0, 보드[0][index] : 2, queue.front(): 2이다.
따라서 현재 칸의 값을 2배로 증가시키고 index를 하나 증가시킨다.
(이동하는 방향이 아래와 오른쪽이라면, index 가 N-1로 시작하여 index-- 연산을 진행해야 한다.)

최종적인 row 0 형태는 세 번째 그림과 같이 4 0 0 0 가 된다.

 

move 함수를 구현했다면, 4방향 선택이 5번 연속된 과정을 브루트 포스 하게 탐색해야 한다.

이때 DFS를 이용하여 5번 선택이 완료될 때마다 현재 보드의 최댓값을 기록되었던 값과 비교하며 최댓값을 업데이트해준다.

DFS 내부에서 for 문을 이용하여 다음 DFS를 호출할 때, 적절하게 보드를 이전 값으로 되돌려야 한다.

이를 위해 copymap을 이용하여 DFS 가 호출되었을 때의 map 상태를 저장하고 다음 DFS를 수행하는 식으로 진행했다.

 

이렇게 모든 경우의 수를 탐색하고 나온 최댓값을 결과로 출력한다.

 

 

소스 코드

#include <iostream>
#include <vector>
#include <queue>
#include <algorithm>

using namespace std;

int N,ans=0;
const int max_N = 20;
int map[max_N][max_N];

void Input(){
    cin >> N;
    for(int i=0; i<N; i++){
        for(int j=0; j<N; j++){
            cin >> map[i][j];
        }
    }
}


//이미 합쳐진 블록이 다시 합쳐지지 않도록 구현해야한다.
//0, 1, 2, 3 순서로 시계방향으로 설정하였다. 0이 12시 방향을 나타낸다.
int dir[4][2] = {{-1,0},{0,1},{1,0},{0,-1}};
void move(int direction){
    queue<int> q;
    if(direction==0){
        //반복문을 통해 각각 col 마다 수행한다.
        for(int j=0; j<N; j++){
            //모든 row 의 값을 탐색하며 0이 아닌 값들을 q 에 넣어준다.
            for(int i=0; i<N; i++){
                if(map[i][j]!=0)
                    q.push(map[i][j]);
                map[i][j]=0;
            }
            //q를 이용하여 덧셈과 이동을 수행한다.
            //1 1 2 2 2 -> 2 4 2 0 0 이 되어야 한다
            //따라서 q 에 기존의 값을 저장한 뒤 순차적으로 꺼내어 진행한다.
            int idx=0;
            while(!q.empty()){
                int value = q.front();
                q.pop();
                //idx 번째 칸이 0인 경우 q 에 있던 제일 앞의 값을 입력한다. 
                //(0 0 4 2 1) -> (4 2 1 0 0) 만들어 주는 과정
                if(map[idx][j]==0)
                    map[idx][j] = value;
                //idx 번째 칸이 q 에 있던 제일 앞의 값과 동일한 경우
                //이 경우는 동일한 두개가 있는 경우로, 두 칸을 더하며 하나로 만든다.
                //이후 idx를 증가시켜 다음칸으로 위치시킨다.
                else if(map[idx][j]==value){
                    map[idx][j] *= 2;
                    idx++;
                }
                //0 도 아니고 값이 다른 경우 idx 를 증가시키고 그 위치에 값을 저장한다.
                else{
                    idx++;
                    map[idx][j] = value;
                }
            }
        }
    }
    //오른쪽
    else if(direction==1){
        for(int i=0; i<N; i++){
            for(int j=N-1; j>=0; j--){
                if(map[i][j]!=0)
                    q.push(map[i][j]);
                map[i][j]=0;
            }
            int idx=N-1;
            while(!q.empty()){
                int value = q.front();
                q.pop();
                if(map[i][idx]==0)
                    map[i][idx] = value;
                else if(map[i][idx]==value){
                    map[i][idx] *= 2;
                    idx--;
                }
                else{
                    idx--;
                    map[i][idx] = value;
                }
            }
        }
    }
    //아래쪽
    else if(direction==2){
        for(int j=0; j<N; j++){
            for(int i=N-1; i>=0; i--){
                if(map[i][j]!=0)
                    q.push(map[i][j]);
                map[i][j]=0;
            }
            int idx=N-1;
            while(!q.empty()){
                int value = q.front();
                q.pop();
                if(map[idx][j]==0)
                    map[idx][j] = value;
                else if(map[idx][j]==value){
                    map[idx][j] *= 2;
                    idx--;
                }
                else{
                    idx--;
                    map[idx][j] = value;
                }
            }
        }
    }
    //왼쪽
    else{
        for(int i=0; i<N; i++){
            for(int j=0; j<N; j++){
                if(map[i][j]!=0)
                    q.push(map[i][j]);
                map[i][j]=0;
            }
            int idx=0;
            while(!q.empty()){
                int value = q.front();
                q.pop();
                if(map[i][idx]==0)
                    map[i][idx] = value;
                else if(map[i][idx]==value){
                    map[i][idx] *= 2;
                    idx++;
                }
                else{
                    idx++;
                    map[i][idx] = value;
                }
            }
        }
    }
}


void DFS(int cnt){
    if(cnt == 5){
        for(int i=0; i<N; i++){
            for(int j=0; j<N; j++){
                ans = max(ans, map[i][j]);
            }
        }
        return;
    }

    //현재 상태 저장
    int copymap[max_N][max_N];
    for(int i=0; i<N; i++){
        for(int j=0; j<N; j++){
            copymap[i][j]=map[i][j];
        }
    }

    for(int i=0; i<4; i++){
        move(i);
        DFS(cnt+1);

        //원래 상태로 복구
        for(int i=0; i<N; i++){
            for(int j=0; j<N; j++){
                map[i][j]=copymap[i][j];
            }
        }
    }
}


int main(){
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

    Input();
    DFS(0);
    cout << ans;
    
    return 0;
}

 

결과 및 후기

브루트 포스 알고리즘이라는 태그를 보고 DFS 방식을 아예 생각하지 못했었는데, DFS를 통해 5번 선택까지의 깊이 탐색으로 모든 과정을 탐색할 수 있었다. 그리고 초기 제출 시 문제의 조건을 잘 확인하지 않아서 시간을 많이 소비했다. 초기 풀이에서의 오점과 브루트 포스 알고리즘을 다른 사람들은 어떻게 구현했나 찾아보던 중 구데타마님의 '꾸준함' 블로그의 포스팅을 보게 되었다. 깔끔했다. 내가 생각했던 논리대로 별다른 주석 없이 이해가 잘 되었다. 다른 분들의 포스팅을 보면서 너무 주석이나 설명이 주저리주저리 많은 것인가 생각도 들고, 다른 사람이 보았을 때 깔끔하게 코드를 짜는 것에 대해서도 생각해보게 되었다.