BOJ_12100_2048(C++) [Brute forcing by DFS]

PS 백준 소스 코드 모음 : https://github.com/kgw4073/Problem-Solving

---

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

12100번: 2048 (Easy)

 이 문제를 꽤나 빨리 풀고 (대략 2-30분) 정답률을 확인하고 조금 놀랐다. 정답률 23%대를 기록하고 있었는데 이 문제가 요구하는 수준이 그 정도인가 하는 생각이 들었다. 그러다가도 필자가 처음 프로그래밍을 시작했을 때, 특히 재귀함수를 통한 완전탐색을 공부할 때 느꼈던 어지러움이 번뜩 떠오르면서 항상 겸손하자는 마음가짐을 되새겼다. Permutation을 C로 짜면서 비주얼 스튜디오 디버그 모드 한 줄씩 실행하기를 통해 3시간 동안 한 줄씩 실행하다가 뇌가 정지되는 마법을 느꼈던 기억을 곱씹어보면 역시 항상 사람은 발전한다는 것을 다시금 깨닫는다.

 아무튼 이 문제는 정말 전형적인 DFS라고 할 수 있다. 전혀 어렵지 않다. 먼저 전체 코드를 소개하고 핵심이 되는 몇 개의 부분만 따로 떼어 설명하겠다. 

#include <iostream>
#include <algorithm>
#include <vector>
 
using namespace std;
 
int n;
int map[20][20];
int answer = 0;
 
// 오른쪽, 왼쪽, 아래쪽, 위쪽
const int dy[] = { 0, 0, 1, -1 };
const int dx[] = { 1, -1, 0, 0 };
 
inline void renew(int map[][20]) {
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            answer = max(answer, map[i][j]);
        }
    }
}
 
void move(int dir, int map[][20]) {
    // 오른쪽
    if (dir == 0) {
        for (int i = 0; i < n; i++) {
            vector<int> vec;
            bool pushflag = false;
            for (int j = n - 1; j >= 0; j--) {
                if (map[i][j]) {
                    if (vec.empty()) {
                        vec.push_back(map[i][j]);
                        pushflag = true;
                    }
                    else {
                        if (vec.back() == map[i][j]) {
                            if (pushflag) {
                                vec.pop_back();
                                vec.push_back(2 * map[i][j]);
                                pushflag = false;
                            }
                            else {
                                vec.push_back(map[i][j]);
                                pushflag = true;
                            }
                        }
                        else {
                            vec.push_back(map[i][j]);
                            pushflag = true;
                        }
                    }
                }
            }
            // map 한 줄 바꿈
            for (int j = n - 1, vecIndex = 0; j >= 0; j--) {
                if (vecIndex != vec.size()) {
                    map[i][j] = vec[vecIndex++];
                }
                else {
                    map[i][j] = 0;
                }
            }
 
        }
    }
    // 왼쪽
    else if (dir == 1) {
        for (int i = 0; i < n; i++) {
            vector<int> vec;
            bool pushflag = false;
            for (int j = 0; j < n; j++) {
                if (map[i][j]) {
                    if (vec.empty()) {
                        vec.push_back(map[i][j]);
                        pushflag = true;
                    }
                    else {
                        if (vec.back() == map[i][j]) {
                            if (pushflag) {
                                vec.pop_back();
                                vec.push_back(2 * map[i][j]);
                                pushflag = false;
                            }
                            else {
                                vec.push_back(map[i][j]);
                                pushflag = true;
                            }
                        }
                        else {
                            vec.push_back(map[i][j]);
                            pushflag = true;
                        }
                    }
                }
            }
            // map 한 줄 바꿈
            for (int j = 0, vecIndex = 0; j < n; j++) {
                if (vecIndex != vec.size()) {
                    map[i][j] = vec[vecIndex++];
                }
                else {
                    map[i][j] = 0;
                }
            }
 
        }
    }
    // 아래쪽
    else if (dir == 2) {
        for (int j = n - 1; j >= 0; j--) {
            vector<int> vec;
            bool pushflag = false;
            for (int i = n - 1; i >= 0; i--) {
                if (map[i][j]) {
                    if (vec.empty()) {
                        vec.push_back(map[i][j]);
                        pushflag = true;
                    }
                    else {
                        if (vec.back() == map[i][j]) {
                            if (pushflag) {
                                vec.pop_back();
                                vec.push_back(2 * map[i][j]);
                                pushflag = false;
                            }
                            else {
                                vec.push_back(map[i][j]);
                                pushflag = true;
                            }
                        }
                        else {
                            vec.push_back(map[i][j]);
                            pushflag = true;
                        }
                    }
                }
            }
            // map 한 줄 바꿈
            for (int i = n - 1, vecIndex = 0; i >= 0; i--) {
                if (vecIndex != vec.size()) {
                    map[i][j] = vec[vecIndex++];
                }
                else {
                    map[i][j] = 0;
                }
            }
 
        }
    }
    // 위쪽
    else {
        for (int j = 0; j < n; j++) {
            vector<int> vec;
            bool pushflag = false;
            for (int i = 0; i < n; i++) {
                if (map[i][j]) {
                    if (vec.empty()) {
                        vec.push_back(map[i][j]);
                        pushflag = true;
                    }
                    else {
                        if (vec.back() == map[i][j]) {
                            if (pushflag) {
                                vec.pop_back();
                                vec.push_back(2 * map[i][j]);
                                pushflag = false;
                            }
                            else {
                                vec.push_back(map[i][j]);
                                pushflag = true;
                            }
                        }
                        else {
                            vec.push_back(map[i][j]);
                            pushflag = true;
                        }
                    }
                }
            }
            // map 한 줄 바꿈
            for (int i = 0, vecIndex = 0; i < n; i++) {
                if (vecIndex != vec.size()) {
                    map[i][j] = vec[vecIndex++];
                }
                else {
                    map[i][j] = 0;
                }
            }
 
        }
    }
}
void solve(int depth, int map[][20]) {
    if (depth == 5) {
        renew(map);
        return;
    }
 
    for (int dir = 0; dir < 4; dir++) {
        int temp[20][20];
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                temp[i][j] = map[i][j];
            }
        }
        move(dir, temp);
        solve(depth + 1, temp);
    }
}
int main() {
    cin.tie(0);
    ios_base::sync_with_stdio(false);
    cin >> n;
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            cin >> map[i][j];
        }
    }
    solve(0, map);
    cout << answer;
}

---

1. DFS 트리 설계

 문제를 보자마자, 현재 상태에서 오른쪽, 왼쪽, 위쪽, 아래쪽 모두 이동할 수 있다는 것에 주목을 해야 한다. 이 사실만 캐치한다면 DFS 트리는 정말 10초만에 머릿속에서 전부 그려질 것이다.

 solve라는 dfs함수를 생각하자. depth는 트리의 깊이를 의미하는데 당연하게도 이것이 움직인 횟수가 되겠다. 이 횟수가 5번이 되면 더 이상 탐색하면 안되니까 현재 map에서 가장 큰 녀석을 고르는 함수 renew를 호출하고 종료한다.

 

 만약 5번에 도달하지 못했다면 계속해서 현재 상태에서 오른쪽, 왼쪽, 위쪽, 아래쪽 모든 방향으로 이동해보고 (move함수 호출) 다음 횟수로 넘어가며 트리를 탐색한다. 이때 주의할 점은 지금 map을 바꿔선 안되므로 temp에 넘겨주고 temp 맵을 트리로 타고 들어간다. 현재 map을 바꾸면 dfs를 타고 들어갔다가 다시 지금 depth로 return해 나왔을 때 계산된 값과 다를 수 있기 때문에 항상 이 map을 보존하기 위해 temp에 따로 담아서 넘겨주어야 한다.

void solve(int depth, int map[][20]) {
    if (depth == 5) {
        renew(map);
        return;
    }
 
    for (int dir = 0; dir < 4; dir++) {
        int temp[20][20];
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                temp[i][j] = map[i][j];
            }
        }
        move(dir, temp);
        solve(depth + 1, temp);
    }
}

---

2. move 함수 설계

 move 함수는 dir에 따라 조금씩 다르지만, 오른쪽으로 움직인다면 열의 가장 오른쪽에 있는 값부터 먼저 움직인다는 것만 생각하면 전혀 어렵지 않다.

 

 * vec에는 각 행에 대해서 이동시킨 결과를 차례대로 저장하며 pushflag는 숫자가 합쳐져도 되는 지를 판단한다.

 

만약 map에 어떤 숫자가 있는데 vec에 아무것도 저장되어 있지 않았다면 그것이 처음 나온 숫자이므로 vec에 저장하고 pushflag를 세팅한다. vec에 무언가 들어가을 때 vec의 마지막 원소와 현재 map에서 탐색하고 있는 숫자가 같다면, push가 가능한지, 즉, 합칠 수 있는지를 판단해야 한다. 이것은 pushflag로 결정하는데 pushflag가 세팅되어 있다면 합쳐도 되며 이때 합치고 나서 pushflag를 다시 false로 초기화해야 한다. 만약 pushflag가 세팅되지 않았다면 합치지 못하며 pushflag를 true로 세팅한다. 이를 코드로 나타내면 다음과 같다.

 

    // 오른쪽
    if (dir == 0) {
        // 각 행에 대해서
        for (int i = 0; i < n; i++) {
            // vec에는 각 행에 대해서 이동시킨 결과를 차례대로 저장
            vector<int> vec;
            // pushflag는 숫자가 합쳐져도 되는 지를 판단
            bool pushflag = false;
            // 오른쪽에 있는 숫자들 먼저 오른쪽으로 이동시킴
            for (int j = n - 1; j >= 0; j--) {
                // map에 뭔가 있을 때
                if (map[i][j]) {
                    // vec이 비어있다면 처음 숫자가 나타난 것
                    if (vec.empty()) {
                        // vec에 넣고 난 후, 같은 숫자가 들어오면 합쳐질 수 있으므로 flag 세팅
                        vec.push_back(map[i][j]);
                        pushflag = true;
                    }
                    // 한 번이라도 숫자가 나왔었다면
                    else {
                        // vec에 마지막 원소와 현재 map에 있는 숫자가 같을 때
                        if (vec.back() == map[i][j]) {
                            // 아직 합쳐지지 않은 것이었다면 합침
                            if (pushflag) {
                                vec.pop_back();
                                vec.push_back(2 * map[i][j]);
                                pushflag = false;
                            }
                            // 이미 합쳐진 것이면 그냥 vec에 담고 flag 세팅
                            else {
                                vec.push_back(map[i][j]);
                                pushflag = true;
                            }
                        }
                        // 숫자 다르면 그냥 vec에 담고 flag 세팅
                        else {
                            vec.push_back(map[i][j]);
                            pushflag = true;
                        }
                    }
                }
            }
            // map 한 줄 갱신. vec에 담겨있는 대로 오른쪽부터 차례대로 저장한다.
            for (int j = n - 1, vecIndex = 0; j >= 0; j--) {
                if (vecIndex != vec.size()) {
                    map[i][j] = vec[vecIndex++];
                }
                else {
                    map[i][j] = 0;
                }
            }
 
        }
    }