[백준알고리즘] 12100번 2048(EASY)

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

으아ㅏㅏ 하다가 도저히 안되어서 다른 분들 것을 참고하였다..

2차원 배열 인자로 넘기고 값 받고 할 때 계속 값이 아니라 주소를 받아와서 애꿎은 값이 변해버리는데 2차원 배열 값 인자로 주고 받는 것을 명확히 이해하고 정리해야겠다.. ㅠㅠ

같은 숫자일 때 그 방향 처음것부터 두개까지만 합치고 다음 index로 넘어가는 것을 구현할 때 실수가 있었는지 내가 했을 때 값이 제대로 나오지 않았다.. 코드도 이상하고 ㅠㅠ 그래서 다른 사람들은 어떤 방식으로 구현하는지 찾아보았는데 굉장히 여러 가지 방법이 있었다.

그 중에 나는 queue를 이용해서 이동해야 하는 곳의 값을 담아둔 후 빼면서 합쳐 갱신하는 방법을 이용해 풀었다!

전체적인 틀은 dfs를 이용하여 모든 경우를 탐색해 최대 값을 찾아내는 것이다!

내가 참고한 분의 블로그 주소를 까먹었는데 그 분 것을 참고하여 이해하고 풀었으니 내 코드가 거의 유사한 코드일 것이당...

나는 방향마다 조건이 달라지는 것을 푸는 데에 어려움을 느끼는 것 같다 ㅠㅠ 각 방향마다 다른 조건일 때 간편하고 가시적으로 푸는 것을 연습해야 겠다..!..

<그림 설명>

<나의 코드>

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

#include<iostream>
#include<queue>
using namespace std;
 
int N, ans;
int board[21][21];
 
// 가장 큰 값을 찾아내는 함수
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;
            }
        }
    }
}
void dfs(int _cnt)
{
    if (_cnt == 5) {
        int local_ans = findmaxvalue();
        if (local_ans > ans) ans = local_ans;
        return;
    }
    
    int temp[21][21] = { 0 };
    copy_arr(temp, board);
 
    for (int i = 0; i < 4; i++)
    {
        direct(i);
        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];
        }
    }
 
    dfs(cnt);
 
    cout << ans;
 
    return 0;
}