[알고리즘] 이차원 배열 중력 작용 (테트리스 블록 떨어트리기)

다음과 같이 높이가 H, 폭이 W인 이차원 배열이 다음과 같을 때 (1은 블럭, 0은 빈 공간)

001100
000000
000111
001111
000000
110111
111011
111101
111110

000000
000000
000000
000100
001111
111111
111111
111111
111111

중력이 작용하듯이 이렇게 아래로 내리는 알고리즘이다.
테트리스에서 한 줄이 지워졌을 때를 생각하면 쉽다.
유의 사항은 아래에 공백(0)이 두 칸 이상이여도 맨 아래로 내려가야한다는 것이다.

전체 탐색 + 빈칸 탐색 풀이

가로줄(W) 탐색 순서는 상관 없고, 맨 아래보다 하나 윗줄 (H - 2)부터 탐색한다.

// 보드를 받아서 중력을 적용한 보드를 반환하는 함수
public int[][] dropBlocks(int[][] board) {
	int H = board.length; // 보드의 세로 길이
	int W = board[0].length; // 보드의 가로 길이
    
    for (int j = 0; j < W; j++) {
        for (int i = H - 2; i >= 0; i--) {
            for (int t = i; t < H - 1; t++) {
                if (board[t][j] != 0 && board[t + 1][j] == 0) {
                    int tmp = board[t][j];
                    board[t][j] = board[t + 1][j];
                    board[t + 1][j] = tmp;
                } else {
                    break;
                }
            }
        }
    }
    return board;
}

해당 칸이 빈칸이 아니고, 해당 칸 바로 아래 칸이 빈칸이라면 둘이 스왑한다.
여러 칸을 떨어질 수도 있으므로 반복문으로 i부터 H - 2 까지 한번 더 돌면서 스왑한다.

시간복잡도는 $O(W * H^2)$ 이다. 보드가 세로로 길 수록 계산 시간이 많이 걸린다. 세로를 한번 더 탐색하는것이 비효율적으로 보인다. 이를 해결해보자.

전체 탐색 + 빈 칸 채우기 풀이

위 풀이와는 다르게 맨 아래줄 부터 보드 전체를 탐색한다.

public int[][] dropBlocks(int[][] board) {
	int H = board.length;
	int W = board[0].length;
	
    for (int j = 0; j < W; j++) {
        int emptyRow = H - 1; // 맨 아래칸을 빈칸이라고 가정
        for (int i = H - 1; i >= 0; i--) {
            if (board[i][j] != 0) { // 현재 칸이 블럭이 있다면
                board[emptyRow][j] = board[i][j]; // 빈 칸에 채우고
                if (emptyRow != i) { // 같은 칸이 아니라면 원래 자리를 0으로 설정 (스왑)
                    board[i][j] = 0;
                }
                emptyRow--; // 한 칸 채웠으니 빈칸을 하나 위로 이동
            }
        }
    }
    return board;
}

블럭을 탐색할 때 매번 아래에 빈칸이 어디까지 있는지 가보는것이 아니라, 각 가로줄에 대하여 맨 아래의 반칸 (emptyRow) 가 어디인지 저장해놓고 그 값을 다음 계산에도 사용한다.

이렇게 하면 시간복잡도가 $O(W * H)$ 이다.

이차원 배열의 블록을 다루는 알고리즘 문제가 많으니 한번쯤 풀이 방법을 생각해놓자.