2차원 배열에 중력이 작용하면?

Introduction

알아두면 쓸모있는 배열 회전의 외전격 게시글입니다. 마찬가지로 코딩 테스트에서 다루는 구현에 대해서 다룹니다.

2차원 배열에서 각 원소에 중력이 작용하면 어떻게 모양이 변할까?

테트리스와 뿌요뿌요 게임을 해보셨다면 이해가 빠르실 겁니다. 하지만 직접 구현하려고 하면 생각보다 손이 꼬일겁니다. 저도 엄청 꼬였습니다.

그래서 배열에 중력이 작용하면 아래로 원소들이 떨어지면서 차곡차곡 쌓이는 함수를 직접 구현해봤습니다. 주의할 점은 각 원소가 모양을 유지하지 않고 떨어진다는 점입니다. 모양을 유지하면서 떨어지려면 배열의 회전 연산을 응용해야하고, 구현이 굉장히 복잡해집니다. 그 부분은 나중에 작성하도록 하겠습니다.

실제 구현

맨 밑에서부터 올라오면서 빈칸이 아닌 지점을 찾습니다. 빈칸이 아닌 지점을 찾고, 만약 빈칸이 아닌 지점보다 밑에 빈칸인 지점이 있다면, 자리를 바꿔줍니다. 빈칸인 지점은 점점 위로 올라오게 되고, 빈칸이 아닌 지점은 아래로 내려가게 됩니다. 크기에 따라 시간복잡도가 커질 수 있으므로, 신중하게 사용해야 합니다.

void gravity(int N, int M, int **A)
{
    for (int y = 0; y < M; y++)
        for (int x = N - 1; x >= 0; x--)
            if (A[x][y] != '.')
                for (int k = N - 1; k > i; k--)
                    if (A[k][j] == '.')
                    {
                        swap(A[i][j], A[k][j]);
                        break;
                    }
}