백준_12100(Easy)

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

문제가 길기 때문에 들어가서 확인하시길!!!

문제 풀이

• nx ,ny :다음 좌표
• x,y :현재 좌표
• 모든 경우를 다 돌아볼때 최대 경우가 O(4^5) 이기 때문에 모든 경우를 다 탐색 가능하다.
• 모든 방향으로 이동할 경우를 재귀로 완전 구현 한다.
• 좌표 이동시에는 이동하려는 방향 끝 지점 부터 탐색한다. (ex. -> 일 경우 , N-1열을 기준으로 줄여 나가면서 행을 탐색한다.)
• 해당 하는 좌표가 숫자 라면 반복문을 통해 이동
  • 다음 지점이 0일 경우에만 계속 이동
  • 다음 지점이 숫자가 같을 경우 합쳐주고 종료 (arr[nx][ny]==arr[ny][ny])
    • 이때, 합친경우에 visited으로 방문처리 해 두번 이상 안 합쳐지게 체킹 후 종료한다.
    • 그외 경우 모두 종료

놓친 점

1. 합쳐진 이후에는 더 이상 이동을 못하기때문에 break해야한다.
2. 모든 좌표를 탐색하는 것이 아닌 '0'이 아닌 좌표만 탐색한다.
3. 중간에 풀이를 수정하다가 한번 갔던 방향으로 이동하면 안되는 것으로 잘못 수정함

• 순회 한 뒤에는 합리셋 되기때문에 같은 방향을 이동해도 된다.(변화되어서 합칠 수 있는 값이 존재 해서!)

순서

1. 시작시에 임시 배열을 초기화 해주면서 재귀를 시작한다.
2. 방향에 따라 ,블록을 이동한다.
   • 모든 좌표를 탐색한다.해당 하는 좌표가 숫자 라면 종료 될때 까지 반복해서 좌표를 옮긴다.
   • 합쳐 질때마다, 최댓 값을 갱신한다.
3. 5회 반복후 종료한다.

 

#include <iostream>
#include <cstring>
using namespace std;
int N;
int ans = 0;
int dx[] = {
    -1, 0, 1, 0}; //순서대로 상우하좌 순
int dy[] = {
    0, 1, 0, -1};
bool check(int x, int y) //범위 벗어나는지 체크
{
    if (x >= 0 && x < N && y >= 0 && y < N)
    {
        return false;
    }
    else
    {
        return true;
    }
}
void copy(int arr[25][25], int temp[25][25]) //베열 초기화 위한 함수
{
    for (int i = 0; i < N; i++)
    {
        for (int j = 0; j < N; j++)
        {
            temp[i][j] = arr[i][j];
        }
    }
}

void go(int arr[25][25], int index, int dir)
{
    int visited[25][25]; //합쳐진지  확인하는 배열
    memset(visited, 0, sizeof(visited));

    if (dir == 0)
    {
        for (int j = 0; j < N; j++)
        {
            for (int i = 0; i < N; i++)
            {
                if (arr[i][j] == 0) //블록일때만 이동
                {
                    continue;
                }
                int x = i;
                int y = j;

                while (true)
                {
                    int nx = x + dx[dir];
                    int ny = y + dy[dir];
                    if (check(nx, ny)) //범위 넘으면 종료
                    {
                        break;
                    }
                    if (arr[nx][ny] == 0) //비어 있을경우 이동
                    {
                        arr[nx][ny] = arr[x][y];
                        arr[x][y] = 0;
                        x = nx;
                        y = ny;
                    }
                    else
                    {
                        if (arr[nx][ny] == arr[x][y] && visited[nx][ny] == 0) //이미 합쳐지지 않고 값이 같을 때
                        {
                            arr[nx][ny] *= 2; //합쳐준뒤에
                            visited[nx][ny] = 1;
                            arr[x][y] = 0;
                        }
                        break; //종료
                    }
                }
            }
        }
    }
    else if (dir == 1)
    {
        for (int i = 0; i < N; i++)
        {
            for (int j = N - 1; j >= 0; j--)
            {
                if (arr[i][j] == 0)
                {
                    continue;
                }
                int x = i;
                int y = j;

                while (true)
                {
                    int nx = x + dx[dir];
                    int ny = y + dy[dir];
                    if (check(nx, ny))
                    {
                        break;
                    }
                    if (arr[nx][ny] == 0)
                    {
                        arr[nx][ny] = arr[x][y];
                        arr[x][y] = 0;
                        x = nx;
                        y = ny;
                    }
                    else
                    {
                        if (arr[nx][ny] == arr[x][y] && visited[nx][ny] == 0)
                        {
                            arr[nx][ny] *= 2;
                            visited[nx][ny] = 1;
                            arr[x][y] = 0;
                            ans = max(ans, arr[nx][ny]); //최댓값 갱신
                        }
                        break;
                    }
                }
            }
        }
    }
    else if (dir == 2)
    {
        for (int i = N - 1; i >= 0; i--)
        {
            for (int j = N - 1; j >= 0; j--)
            {
                if (arr[i][j] == 0)
                {
                    continue;
                }
                int x = i;
                int y = j;

                while (true)
                {
                    int nx = x + dx[dir];
                    int ny = y + dy[dir];
                    if (check(nx, ny))
                    {
                        break;
                    }
                    if (arr[nx][ny] == 0)
                    {
                        arr[nx][ny] = arr[x][y];
                        arr[x][y] = 0;
                        x = nx;
                        y = ny;
                    }
                    else
                    {
                        if (arr[nx][ny] == arr[x][y] && visited[nx][ny] == 0)
                        {
                            arr[nx][ny] *= 2;
                            visited[nx][ny] = 1;
                            arr[x][y] = 0;
                            ans = max(ans, arr[nx][ny]);
                        }
                        break;
                    }
                }
            }
        }
    }
    else
    {
        for (int i = 0; i < N; i++)
        {
            for (int j = 0; j < N; j++)
            {
                if (arr[i][j] == 0)
                {
                    continue;
                }
                int x = i;
                int y = j;

                while (true)
                {
                    int nx = x + dx[dir];
                    int ny = y + dy[dir];
                    if (check(nx, ny))
                    {
                        break;
                    }
                    if (arr[nx][ny] == 0)
                    {
                        arr[nx][ny] = arr[x][y];
                        arr[x][y] = 0;
                        x = nx;
                        y = ny;
                    }
                    else
                    {
                        if (arr[nx][ny] == arr[x][y] && visited[nx][ny] == 0)
                        {
                            arr[nx][ny] *= 2;
                            visited[nx][ny] = 1;
                            arr[x][y] = 0;
                            ans = max(ans, arr[nx][ny]);
                        }
                        break;
                    }
                }
            }
        }
    }

    if (index == 5)
    {
       
        return;
    }

    int temp[25][25];
    copy(arr, temp);
    go(temp, index + 1, 0);

    copy(arr, temp);
    go(temp, index + 1, 1);

    copy(arr, temp);
    go(temp, index + 1, 2);

    copy(arr, temp);
    go(temp, index + 1, 3);
}
int main()
{
    cin >> N;
    int arr[25][25];
    for (int i = 0; i < N; i++)
    {
        for (int j = 0; j < N; j++)
        {
            cin >> arr[i][j];
            ans = max(arr[i][j], ans);
        }
    }
    int temp[25][25];
    copy(arr, temp);
    go(temp, 1, 0);
    copy(arr, temp);
    go(temp, 1, 1);
    copy(arr, temp);
    go(temp, 1, 2);
    copy(arr, temp);
    go(temp, 1, 3);
    cout << ans << '\n';
    return 0;
}