[백준알고리즘] 12094번 2048(HARD)

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

나에게 똥을 준 문제.. ㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋ 거의 정신 놓고 풀었음...

하도하도 안되서 다른 분들 것을 참고하였다...

정답 비율에 일조한 나의 채점 현황^^* 워매 힘든거..

dfs를 이용하여 완전탐색으로 특정 조건이 되었을 때 최대값을 찾는 문제이다!

2048(EASY)와는 다르게 2048(HARD)는 count가 10까지 가야하기 때문에 수행시간을 줄이는 것이 핵심이 되는 문제이다!!

<수행시간을 줄이기 위해 내가 생각했던 방법들>

첫 번째로, 모든 count 마다의 board에 대한 visited 배열을 만들어서 저장된 최댓값보다 현재가 작은 값인 경우 가지 않는 것으로 구현하려 했다.

ex) 4번 이동해서 1024가 나온 것이 저장된 최대값인데, 지금 4번 이동해서 512가 나왔으면 더 이상 하지 않아도 되기 때문!

visited는 각 count마다 저장된 방문한 보드판

visited[count][board_value];

count와 각 배열의 위치의 값마다 다른 경우라는 것을 저장하기 위해 ((각 인덱스*배열의 값)을 모두 더한 것) 의 크기만큼 board_value를 결정하고자 하였다. 

그런데 초기값이 1024에 20*20 행렬 이면 board_value의 크기가 매우매우 커져버려서 컴파일 에러, 메모리 초과 등이 나기 때문에 이 방법은 실행할 수 없는 방법이었다.. 

두 번째로, 상하좌우로 이동하였을 때, 이전의 board와 완전히 일치한다면 count를 하나 늘려서 같은 board의 경우로 갈 필요가 없기 때문에 이러한 경우를 제외시키는 것을 생각하였다.

그러나 이 방법만 사용했을 때에는 여전히 시간 초과가 났다 ㅠㅠ!

세 번째로, 첫 번째 방법을 변경하여 board 자체에 대한 visited를 만들지 않고 최대값에 대한 visited를 만들었다.

ex) ans는 각 count마다 저장된 최대값

ans[count]

계속 현재 count에서의 board의 최대값을 찾아 ans[count]에 저장된 값과 비교하여 진행 여부를 찾는 방식이었다.

그러나 이 방법 역시 문제를 완전히 해결해 주지 못했다.

계속 해도 도저히 이제 모르겠어서 ㅠㅠ 다른 사람들의 코드를 참고하였다.

시간을 줄이는 방법의 핵심 조건은 두 가지였다.

1) 상하좌우 이동시 board가 변경되지 않으면 그 방향은 진행하지 않는다.

2) 현재 최대값에서 10번 움직였을 때의 최대값에 도달할 수 없는 경우 되돌아간다.

내가 생각한 방법과 유사하다고 생각하며 위 방법들을 참고하여 다시 코드를 짜봐도 계속 시간초과가 났다 ㅠㅠㅠㅠ

그러다가 결국 내가 제대로 캐치하지 못했던 것 몇 가지를 알 수 있었다!!!!!

1) N = 1일 때, 나의 코드에서는 보드가 갱신될 수 없었으므로 count = 10까지 가지 않는다. 이에 대한 예외처리가 필요하다.

2) 최대값에 도달할 수 없는 경우를 찾기 위해, N =10이 아닐 때, 현재 최대값이 가져야 하는 값을 / 를 하며 찾아나갔는데 나눗셈 연산을 지속적으로 하는 게 시간 초과의 원인이 되었다.  따라서 N = 10일 때, 나눈 값을 저장해 놓고 사용함으로써 해결할 수 있었다. 

시간 초과 문제 해결하느라 정말 힘들었다..ㅠㅠ 이 문제는 나중에 꼭 다시 재점검하면서 핵심적인 부분을 찾아내서 코딩할 수 있도록 연습해야겠다!!!

<그림 설명>

<나의 코드>

https://github.com/j2wooooo/Daliy_Algorithms/blob/master/Daliy_Algorithms/BOJ_12094/BOJ_12094.cpp

#include<iostream>
#include<queue>
using namespace std;
 
int N;
int ans;
bool flag;
int board[21][21];
int threshold_value[11];
 
// 최소값을 구하는 함수
int findmaxvalue()
{
    int val = 0;
    for (int i = 0; i < N; i++)
    {
        for (int j = 0; j < N; j++)
        {
            if (board[i][j] > val) val = board[i][j];
        }
    }
    return val;
}
 
// 배열의 값을 복사하는 함수
void copy_arr(int(*temp)[21], int(*board)[21])
{
    for (int i = 0; i < N; i++)
    {
        for (int j = 0; j < N; j++)
        {
            *(temp[i] + j) = *(board[i] + j);
        }
    }
    return;
}
 
// 4방향을 탐색하는 함수
void direct(int dir)
{
    queue<int> q; // board의 값을 넣을 queue
 
    if (dir == 0) // UP
    {
        for (int j = 0; j < N; j++)
        {
            for (int i = 0; i < N; i++)
            {
                if (board[i][j]) {
                    // 0 이 아니면 값을 queue에 넣고 board의 값을 0 으로 채운다.
                    q.push(board[i][j]);
                    board[i][j] = 0;
                }
            }
            int idx = 0;
            // 모든 값을 빼내면서
            while (!q.empty())
            {
                int val = q.front();
                q.pop();
 
                // board의 값이 0 이면 그 자리에 queue에 넣었던 값을 넣는다.
                if (!board[idx][j]) board[idx][j] = val;
                // board의 값이 queue의 값과 같다면 두 값을 합쳐 넣고 위치를 한 칸 이동시킨다.
                else if (board[idx][j] == val) board[idx++][j] += val;
                // board의 값이 queue의 값과 다르다면 다음 위치로 한 칸 이동시켜 값을 넣는다.
                else if (board[idx][j]) board[++idx][j] = val;
            }
        }
    }
    else if (dir == 1) // DOWN
    {
        for (int j = 0; j < N; j++)
        {
            for (int i = N - 1; i >= 0; i--)
            {
                if (board[i][j]) {
                    q.push(board[i][j]);
                    board[i][j] = 0;
                }
            }
            int idx = N - 1;
            while (!q.empty())
            {
                int val = q.front();
                q.pop();
 
                if (!board[idx][j]) board[idx][j] = val;
                else if (board[idx][j] == val) board[idx--][j] += val;
                else if (board[idx][j]) board[--idx][j] = val;
            }
        }
    }
    else if (dir == 2) // LEFT
    {
        for (int i = 0; i < N; i++)
        {
            for (int j = 0; j < N; j++)
            {
                if (board[i][j]) {
                    q.push(board[i][j]);
                    board[i][j] = 0;
                }
            }
            int idx = 0;
            while (!q.empty())
            {
                int val = q.front();
                q.pop();
 
                if (!board[i][idx]) board[i][idx] = val;
                else if (board[i][idx] == val) board[i][idx++] += val;
                else if (board[i][idx]) board[i][++idx] = val;
            }
        }
    }
    else if (dir == 3) // RIGHT
    {
        for (int i = 0; i < N; i++)
        {
            for (int j = N - 1; j >= 0; j--)
            {
                if (board[i][j]) {
                    q.push(board[i][j]);
                    board[i][j] = 0;
                }
            }
            int idx = N - 1;
            while (!q.empty())
            {
                int val = q.front();
                q.pop();
 
                if (!board[i][idx]) board[i][idx] = val;
                else if (board[i][idx] == val) board[i][idx--] += val;
                else if (board[i][idx]) board[i][--idx] = val;
            }
        }
    }
}
bool compare_arr(int (*temp)[21], int (*board)[21])
{
    for (int j = 0; j < N; j++)
    {
        for (int k = 0; k < N; k++)
        {
            if (temp[j][k] != board[j][k]) return true;
        }
    }
    return false;
}
void dfs(int _cnt)
{
    int val = findmaxvalue();
 
    if (val <= threshold_value[_cnt]) return; // 현재 count에서 최대값 만드는게 불가능
 
    // count 10번째까지 오면
    // count마다 가져야할 최소값을 갱신한다.
    if (_cnt == 10) {
        ans = max(ans, val);
        int v = ans;
        while (_cnt > 0) {
            threshold_value[_cnt--] = v;
            v /= 2;
        }
        return;
    }
 
    int temp[21][21] = { 0 };
    copy_arr(temp, board);
 
    for (int i = 0; i < 4; i++)
    {
        direct(i);
 
        flag = compare_arr(temp, board);
 
        if (flag) {
            dfs(_cnt + 1);
            copy_arr(board, temp);
        }
    }
    return;
}
 
int main()
{
    int cnt = 0;
 
    cin >> N;
 
    for (int i = 0; i < N; i++)
    {
        for (int j = 0; j < N; j++)
        {
            cin >> board[i][j];
        }
    }
 
    ans = findmaxvalue();
 
    dfs(cnt);
 
    cout << ans;
 
    return 0;
}