[백준 12094] 2048(hard)

풀이 방법

이 문제는 시간 초과를 해결하는 게 관건인 문제였다.

기존에 2048(easy) 문제를 풀 때 완 탐으로 풀었었는데 가지를 쳐서(백트래킹 이용) 시간을 줄이는 방법으로 풀었다.

 

 

시간 초과 해결법 - 백트래킹을 이용한다.

1. 진행할 때 단계별 최댓값을 미리 계산하여 불가능한 경우 더 이상 진행하지 않는다.
2. 이동하여 맵이 같은 경우 더 이상 진행하지 않는다.

여기서 시간 초과 해결법 2번의 경우에 의해 예외처리를 제대로 해주지 않아 많이 헤맸다.

이유는 가장 큰 블록의 최신화를 항상 cnt==10 일 때 해주었었는데 그 때문에 움직이지 못하는 경우에 0으로 뽑히는 문제가 있었다.

 

반례가 나왔던 예

4
2 4 8 16
4 8 16 32
8 16 32 64
16 32 64 128
정답 : 128
내 기존답 : 0

위의 경우에는 이동이 불가능한 경우다 그래서 맵이 같은 경우를 넘겨버리는 내 시간 초과 해결법 때문에 dfs depth가 10까지는 물론 증가 자체가 불가능한 경우다. 이러한 경우 때문에 max값 최신화 타이밍을 dfs 호출 후 현재 맵의 최댓값 탐색 후로 변경하였다.

 

 

소스코드

#include <stdio.h>
#include<stdlib.h>
#include <queue>
#include <algorithm>
#define MAX_SIZE 21
#define UP 0
#define RIGHT 1
#define DOWN 2
#define LEFT 3
using namespace std;
 
 
int N;
int Map[MAX_SIZE][MAX_SIZE];
void copy_map(int(*arr)[MAX_SIZE], int(*arr2)[MAX_SIZE]);
void slide_map(int d);
void DFS(int cnt);
int getMax();
bool isChanged(int(*temp)[MAX_SIZE]);
int branch_max[11];
int max_block;
int main() {
    scanf("%d", &N);
    for (int i = 0; i < N; i++) {
        for (int j = 0; j < N; j++) {
            scanf("%d", &Map[i][j]);
        }
    }
    DFS(0);
    //int max_val = getMax();
    //max_block = max(max_block, max_val);
    printf("%d\n", max_block);
 
 
}
void DFS(int cnt) {
    int temp[MAX_SIZE][MAX_SIZE];
    
    int max_val = getMax();
    max_block = max(max_block, max_val);
    if (max_val <= branch_max[cnt])
        return;
 
    if (cnt == 10) {
        int branch_max_value = max_block;
        while (cnt > 0) {
            branch_max[cnt] = branch_max_value;
            cnt--;
            branch_max_value /= 2;
        }
        return;
    }
 
    copy_map(temp, Map);
 
    for (int i = 0; i < 4; i++) {
        slide_map(i);
        if (isChanged(temp)) {
            DFS(cnt + 1);
        }
        
        //다시 원상복구
        copy_map(Map, temp);
    }
 
}
void copy_map(int(*arr)[MAX_SIZE], int(*arr2)[MAX_SIZE]) {
    for (int i = 0; i < N; i++) {
        for (int j = 0; j < N; j++) {
            arr[i][j] = arr2[i][j];
        }
    }
}
void slide_map(int d) {
    queue<int> q;
    int next_row, next_col;
    int index;
    int data;
 
    switch (d) {
    case UP://위
        for (int i = 0; i < N; i++) {//col로 돌리기
            for (int j = 0; j < N; j++) {//row로 돌리기
                if (Map[j][i] != 0) {
                    q.push(Map[j][i]);
                }
                Map[j][i] = 0;
            }
            index = 0;
 
            while (!q.empty()) {
                data = q.front();
                q.pop();
 
                if (Map[index][i] == 0)
                    Map[index][i] = data;
                else if (Map[index][i] == data) {//데이터가있는데 값도 같아서 합쳐야되는 경우
                    Map[index][i] *= 2;
                    index++;//이걸로 여러번 합쳐지는걸 막음
                }
                else {//데이터가 있는데 값이 다른경우
                    index++;
                    Map[index][i] = data;
                }
            }
        }
        break;
    case LEFT:
        for (int i = 0; i < N; i++) {//row로 돌리기
            for (int j = 0; j < N; j++) {//col로 돌리기
                if (Map[i][j] != 0) {
                    q.push(Map[i][j]);
                }
                Map[i][j] = 0;
            }
            index = 0;
 
            while (!q.empty()) {
                data = q.front();
                q.pop();
 
                if (Map[i][index] == 0)
                    Map[i][index] = data;
                else if (Map[i][index] == data) {//데이터가있는데 값도 같아서 합쳐야되는 경우
                    Map[i][index] *= 2;
                    index++;//이걸로 여러번 합쳐지는걸 막음
                }
                else {//데이터가 있는데 값이 다른경우
                    index++;
                    Map[i][index] = data;
                }
            }
        }
        break;
    case RIGHT://오른
        for (int i = 0; i < N; i++) {//row로 돌리기
            for (int j = N - 1; j >= 0; j--) {//col로 돌리기
                if (Map[i][j] != 0) {
                    q.push(Map[i][j]);
                }
                Map[i][j] = 0;
            }
            index = N - 1;
 
            while (!q.empty()) {
                data = q.front();
                q.pop();
 
                if (Map[i][index] == 0)
                    Map[i][index] = data;
                else if (Map[i][index] == data) {//데이터가있는데 값도 같아서 합쳐야되는 경우
                    Map[i][index] *= 2;
                    index--;//이걸로 여러번 합쳐지는걸 막음
                }
                else {//데이터가 있는데 값이 다른경우
                    index--;
                    Map[i][index] = data;
                }
            }
        }
        break;
    case DOWN:
        for (int i = 0; i < N; i++) {//col로 돌리기
            for (int j = N - 1; j >= 0; j--) {//row로 돌리기
                if (Map[j][i] != 0) {
                    q.push(Map[j][i]);
                }
                Map[j][i] = 0;
            }
            index = N - 1;
 
            while (!q.empty()) {
                data = q.front();
                q.pop();
 
                if (Map[index][i] == 0)
                    Map[index][i] = data;
                else if (Map[index][i] == data) {//데이터가있는데 값도 같아서 합쳐야되는 경우
                    Map[index][i] *= 2;
                    index--;//이걸로 여러번 합쳐지는걸 막음
                }
                else {//데이터가 있는데 값이 다른경우
                    index--;
                    Map[index][i] = data;
                }
            }
        }
        break;
 
    }
 
}
int getMax() { //map에서 가장 큰수 반환
    int max_val = 0;
    for (int i = 0; i < N; i++) {
        for (int j = 0; j < N; j++) {
            max_val = max(max_val, Map[i][j]);
        }
    }
    return max_val;
}
bool isChanged(int(*temp)[MAX_SIZE]) {
    for (int i = 0; i < N; i++) {
        for (int j = 0; j < N; j++) {
            if (Map[i][j] != temp[i][j])
                return true;
        }
    }
    return false;
}

 

문제 링크 : https://www.acmicpc.net/problem/12094

12094번: 2048 (Hard)