백준 12100 2048(Easy) :: 들짐승

<링크>

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

<풀이>

시키는 대로 하면된다.

1.큰그림

재귀로 풀었는데
판때기 상태를 나타내는 2차원 배열을 인자로 받아서

4가지방향(상하좌우)로 이동시킨 모습으로 수정하고
그대로 재귀호출로 넘겨주는 방식이다.

'상' 방향으로 배열을 수정할 때 인자로 받은 배열은 call by reference이기 때문에 그대로 수정하면 맨위에있는 배열이 바뀌게 되고, 다른 방향들을 볼 때 전혀 다른 결과가 되기 때문에

함수가 호출될 때마다 인자로 넘어온 배열을 복사해서 진행했다. 
그럼 각 함수 호출마다 20*20 int배열이 필요하게 된다. 재귀호출된 depth가 깊어질 수록 메모리 사용이 커지는데   배열로만 스택에 4^depth * 400 * sizeof(int)  byte만큼의 메모리를 쓰게 된다. 
문제에 최대 5회라고 되어있으니깐 충분할 것 같아서 진행했다.

2. 각 방향으로 이동할 때

2중 for문을 돌면서 모두 체크한다.
0이 아닌 숫자가 뜨면, 내가 가는 방향으로 바로 다음 칸이 0일 때까지 쭉 간다.
그 후 다음 칸의 숫자랑 나랑 같으면 더해서 다음 칸의 숫자를 만들고 나는 0으로 없애버린다.
이 때, 한 번의 이동에서 두 번이상 더해질 수 없으므로 해당 칸의 숫자가 변했는지 체크하기 위한 배열을 또 만들었다. 이 때문에 메모리 사용이 2배로 더 늘어났을 것이다.

3. 코드를 줄이기 위한 나의 최선

똑같은 수가 세 개가 있는 경우에는 이동하려고 하는 쪽의 칸이 먼저 합쳐지기 때문에 각 방향마다 
2중 for문으로 탐색하는 순서가 달라야 한다.
상, 좌 방향은 판의 왼쪽위부터 우리가 평소하는 2중for문 순서대로 훑으면 되고
우, 하 방향은 판의 오른쪽 아래부터 반대로 훑어야한다.
toI,toJ[4]배열을 만들었다.

<소스코드>

#include<stdio.h>
int pan[20][20];
int N;
int toI[4] = { -1,1,0,0 }; //상하좌우
int toJ[4] = { 0,0,-1,1 };
int ans;
void dfs(int(*)[20], int);
void progress1(int(*)[20], int, int);
void progress2(int(*)[20], int, int);
void arrCpy(int(*)[20], int(*)[20]);
int main()
{
    scanf("%d", &N);
 
    for (int i = 0; i < N; ++i) //상,좌
        for (int j = 0; j < N; ++j) {
            scanf("%d", &pan[i][j]);
            if (pan[i][j] > ans)
                ans = pan[i][j];
        }
    dfs(pan, 0);
    printf("%d", ans);
}
void dfs(int(*p)[20], int depth)
{
    if (depth == 5)
        return;
    for (int k = 0; k < 4; ++k)
    {
        int tmpArr[20][20] = { 0, };
        arrCpy(tmpArr, p);
        if (k % 2 == 0)
            progress1(tmpArr, toI[k], toJ[k]);
        else
            progress2(tmpArr, toI[k], toJ[k]);
        dfs(tmpArr, depth + 1);
    }
    return;
}
void progress1(int(*a)[20], int toi, int toj) //상,좌
{
    int check[20][20] = { 0, }; //한번 합쳐진 좌표인지 확인용
    for (int i = 0; i < N; ++i) //상,좌
        for (int j = 0; j < N; ++j)
            if (a[i][j] != 0)
            {
                int curi = i;
                int curj = j;
                int tmp = a[curi][curj];
                while (curi + toi >= 0 && curj + toj >= 0 && a[curi + toi][curj + toj] == 0)
                {
                    a[curi][curj] = 0;
                    curi += toi;
                    curj += toj;
                }
                a[curi][curj] = tmp;
                if (curi + toi >= 0 && curj + toj >= 0
                    && a[curi + toi][curj + toj] == a[curi][curj]
                    &&!check[curi+toi][curj+toj])
                {
                    int sum = a[curi + toi][curj + toj] + a[curi][curj];
                    if (sum > ans)
                        ans = sum;
                    a[curi + toi][curj + toj] = sum;
                    check[curi + toi][curj + toj] = 1;
                    a[curi][curj] = 0;
                }
 
            }
 
 
}
void progress2(int(*a)[20], int toi, int toj) //우,하
{
    int check[20][20] = { 0, }; //한번 합쳐진 좌표인지 확인용
    for (int i = N - 1; i >= 0; --i) //우,하
        for (int j = N - 1; j >= 0; --j)
            if (a[i][j] != 0)
            {
                int curi = i;
                int curj = j;
                int tmp = a[curi][curj];
                
                while (curi + toi <N && curj + toj < N && a[curi + toi][curj + toj] == 0)
                {
                    a[curi][curj] = 0;
                    curi += toi;
                    curj += toj;
                }
                a[curi][curj] = tmp;
                if (curi + toi <N && curj + toj<N
                    && a[curi + toi][curj + toj] == a[curi][curj]
                    && !check[curi + toi][curj + toj])
                {
                    int sum = a[curi + toi][curj + toj] + a[curi][curj];
                    if (sum > ans)
                        ans = sum;
                    a[curi + toi][curj + toj] = sum;
                    check[curi + toi][curj + toj] = 1;
                    a[curi][curj] = 0;
                }
 
            }
}
void arrCpy(int(*a)[20], int(*b)[20])
{
    for (int i = 0; i < N; ++i)
        for (int j = 0; j < N; ++j)
            a[i][j] = b[i][j];
}