[Algorithm] Baekjoon 12100번 : 2048(Easy)

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

12100번: 2048 (Easy)

int n;
int arr[22][22] = { 0 };
int tempArr[22][22] = { 0 };
bool visited[22][22] = { false };
int dirs[4][2] = { {-1,0}, {1,0}, {0,-1}, {0,1} };
vector<int> curDirs;
int answer = 0;
 
void move(int y, int x, int dir)
{
    int num = tempArr[y][x];
    tempArr[y][x] = 0;
 
    int nextY = y + dirs[dir][0];
    int nextX = x + dirs[dir][1];
 
    while (tempArr[nextY][nextX] != -1 && tempArr[nextY][nextX] == 0) // 이동가능하면
    {
        y = nextY;
        x = nextX;
        nextY += dirs[dir][0];
        nextX += dirs[dir][1];
    }
 
    if (tempArr[nextY][nextX] == num && !visited[nextY][nextX])
    {
        tempArr[nextY][nextX] *= 2;
        visited[nextY][nextX] = true;
        answer = max(answer, tempArr[nextY][nextX]);
    }
    else
    {
        tempArr[y][x] = num;
    }
}
 
void traversalLoop(int dir)
{
    switch (dir)
    {
    case 0:
        for (int i = 1; i <= n; ++i)
        {
            for (int j = 1; j <= n; ++j)
            {
                if (tempArr[i][j] != 0) move(i, j, dir);
            }
        }
        break;
 
    case 1:
        for (int i = n; i >= 1; --i)
        {
            for (int j = 1; j <= n; ++j)
            {
                if (tempArr[i][j] != 0) move(i, j, dir);
            }
        }
        break;
 
    case 2:
        for (int i = 1; i <= n; ++i)
        {
            for (int j = 1; j <= n; ++j)
            {
                if (tempArr[j][i] != 0) move(j, i, dir);
            }
        }
        break;
 
    case 3:
        for (int i = n; i >= 1; --i)
        {
            for (int j = 1; j <= n; ++j)
            {
                if (tempArr[j][i] != 0) move(j, i, dir);
            }
        }
        break;
    }
}
 
void DFS()
{
    if (curDirs.size() == 5)
    {
        memcpy(tempArr, arr, sizeof(arr));
        
        for (int i = 0; i < 5; ++i)
        {
            memset(visited, false, sizeof(visited));
            traversalLoop(curDirs[i]);
        }
 
        return;
    }
 
    for (int i = 0; i < 4; ++i)
    {
        curDirs.push_back(i);
        DFS();
        curDirs.pop_back();
    }
}
 
int main(void)
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
 
    cin >> n;
 
    memset(arr, -1, sizeof(arr));
 
    for (int i = 1; i <= n; ++i)
    {
        for (int j = 1; j <= n; ++j)
        {
            cin >> arr[i][j];
            answer = max(answer, arr[i][j]);
        }
    }
 
    DFS();
 
    cout << answer;
}

괜시리 각 방향마다 for문 돌리는것을 뭔가 굉장히 짧고 깔끔하게 짜려다 시간만 진창 날린문제.

항상 후회하는 것 같다. 물론 시도가 나쁜건 아니지만, 일단 통과시킨다음 고치던가 했어야했다.

중복순열로 각 차례마다 어떤방향으로 이동시킬지 방향을 전부 뽑고 이동시키면 된다.

 

주의할 점은, 이미 합쳐진건 또 합치면 안된다는걸 명심해야 한다. 나같은경우 그냥 visited 따로 선언해서 체크했다.