[BOJ] 백준 19235 모노미노도미노

출처: https://www.acmicpc.net/problem/19235

 Input 

8

1 1 1

2 3 0

3 2 2

3 2 3

3 1 3

2 0 0

3 2 0

3 1 2

　 

 Output 

3

11

해당 문제에 앞서 [BOJ] 20061 모노미노도미노 2를 먼저 보시길 권장합니다.

[BOJ] 백준 20061 모노미노도미노 2

두 문제의 차이는 특정 행에서 블록이 가득차서 삭제한 후, 위쪽에 있는 블록을 어떻게 처리하는가 입니다.

[BOJ] 20061 모노미노도미노 2는 단순히 삭제되는 행 위에 위치한 행들을 한줄씩 내려오게 했으면 되었지만

해당 문제는 내려올 수 있는 블록은 경계선까지 최대한 내려오게 되는 내용입니다.

위와 같은 경우에는 빨간 블록이 내려올 때, 걸쳐있기에 두번째 그림 단계까지만 진행됩니다.

 

코드 분석

※ [BOJ] 20061 모노미노도미노 2와의 차이있는 부분을 우선적으로 작성

x번 행을 시작으로 해당 블록이 type에 따라 최대한 떨어질 수 있는 곳을 확인합니다.

- 빨간색 영역에서 블록을 처음 떨어뜨리는 경우에는 제일 위에서 부터 탐색해야 하기에 x = 0이지만

   꽉찬 행을 처리한 후 블록을 떨어뜨리기 위해 x인자를 추가하였습니다.

   

※ 어떤 type인지 알아내기 위해서 블록 표시를 단순히 "1"로 하지않고 "id" 형태로 저장합니다.

 

특정 행을 삭제한 후, 위에 위치한 블록들을 떨어뜨릴때, 아래와 같은 탐색 순서와 방향을 가집니다.

따라서 해당 블록(area[][r][c])이 어떤 타입인지 확인하는 방법은 아래와 같습니다.

오른쪽(type 2)과 위쪽(type 3)을 확인해서 존재하는 경우 해당 type 반환

(테트리스가 진행되다보면 처음 주어진 블록 type이 변형될 수 있기 때문에 BFS 형식으로 확인합니다.)

※ 블록 id를 바탕으로 block[id]를 관리해서 type, 위치, 존재유무를 확인할 수도 있지만 

    6×4 영역이기 때문에 구현의 난이도면에서 비효율적입니다.

 

기존 블록의 위치를 비워준 후, 기존 위치에서 블록을 떨어뜨립니다.

drop(type, r, c, color, id); 

걸처있는 등 경우에 따라서는 다시 기존 위치에 존재할 수 있습니다.

 

---

#include <stdio.h>
enum {
    EMPTY = 0,
    GREEN = 0,
    BLUE = 1,
    FULL = 4,
};
int N, type, x, y, ans;
int area[2][6][4];
const int dx[] = { 0, 0, 0, -1 };
const int dy[] = { 0, 0, 1,  0 };
 
void drop(int type, int x, int y, int color, int id) {
    int insert;
    if (type == 1 || type == 3) {
        for (insert = x; insert < 6; ++insert) {
            if (area[color][insert][y] != EMPTY)
                break;
        }
        insert--;
        area[color][insert][y] = id;
        if (type == 3) area[color][insert - 1][y] = id;
    }
    else { // type == 2
        for (insert = x; insert < 6; ++insert) {
            if (area[color][insert][y] != EMPTY
                || area[color][insert][y + 1] != EMPTY)
                break;
        }
        insert--;
        area[color][insert][y] = id;
        area[color][insert][y + 1] = id;
    }
}
 
int getType(int color, int r, int c) {
    // 위쪽, 오른쪽
    for (int type = 2; type <= 3; ++type) {
        int nextR = r + dx[type];
        int nextC = c + dy[type];
        if (nextR < 0 || nextC >= 4) continue;
        if (area[color][nextR][nextC] == area[color][r][c])
            return type;
    }
    return 1; // type 1
}
 
void remove(int color, int row) {
    // 삭제되는 줄을 비웁니다.
    for (int c = 0; c < 4; c++) {
        area[color][row][c] = EMPTY;
    }
 
    // 현재 row 기준 위쪽에 블록들이
    // 내려올 수 있는 위치까지 내려오게 만듭니다.
    for (int r = row - 1; r >= 0; --r) {
        for (int c = 0; c < 4; ++c) {
            if (area[color][r][c] > 0) {
                int id = area[color][r][c];
                int type = getType(color, r, c);
                // 원래 도형위치를 지웁니다.
                area[color][r][c] = EMPTY;
                // type == 2, 3인 경우 다른 부분도 지웁니다.
                if (type == 2) area[color][r][c + 1] = EMPTY;
                else if (type == 3) area[color][r - 1][c] = EMPTY;
                drop(type, r, c, color, id);
            }
        }
    }
}
 
void checkFull(int color) {
    for (int r = 2; r < 6; ++r) {
        int cnt = 0;
        for (int c = 0; c < 4; ++c) {
            // 블록이 존재하는 경우
            if (area[color][r][c] > 0) cnt++;
        }
        if (cnt == FULL) {
            remove(color, r);
            ans++;
        }
    }
}
 
void checkLightArea(int color) {
    for (int r = 0; r <= 1; ++r) {
        for (int c = 0; c < 4; ++c) {
            if (area[color][r][c] > 0) {
                remove(color, 5);
                break;
            }
        }
    }
}
 
int main() {
    // freopen("input.txt", "r", stdin);
    scanf("%d", &N);
    for (int i = 1; i <= N; ++i) {
        scanf("%d %d %d", &type, &x, &y);
        drop(type, 0, y, GREEN, i);
        if (type == 1) drop(1, 0, 4 - x - 1, BLUE, i);
        else if (type == 2) drop(3, 0, 4 - x - 1, BLUE, i);
        else drop(2, 0, 4 - (x + 1) - 1, BLUE, i);
 
        checkFull(GREEN);
        checkFull(BLUE);
 
        checkLightArea(GREEN);
        checkLightArea(BLUE);
    }
    printf("%d\n", ans);
 
    int blockCnt = 0;
    for (int color = GREEN; color <= BLUE; color++) {
        for (int r = 2; r < 6; ++r) {
            for (int c = 0; c < 4; ++c) {
                if (area[color][r][c] > 0) blockCnt++;
            }
        }
    }
    printf("%d\n", blockCnt);
}