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

삼성 SW 코딩 테스트 준비(A형)

삼성 SW 기출 모음

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

 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 

2

15

　

※ 이 문제는 [BOJ] 19235 모노미노도미노 보다 쉽게 구현할 수 있습니다.

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

이번 문제는 조금 특이한(?) 테트리스를 구현하는 문제입니다.

일반적인 테트리스와 달리 해당 문제에서는 한 줄이 채워진 경우에는

위에 있는 줄이 있는 그대로 내려오면 된다는 것입니다.

* 초록색 영역과 파랑색 영역을 구현할 때, 테트리스 원리는 동일하기 때문에 행/열만 다르게 생각해서

   구현가능하며, 해당 글에서는 파랑색 영역을 마치 왼쪽으로 90도 회전한 것처럼해서

   초록색 영역과 동일하게 처리합니다.

 

① 블록을 떨어뜨립니다.

- area[green/blue][6][4]로 정의

- type = 1, 3은 바로 아래 위치에 블록만 존재하지 않는 경우 계속 아래로 떨어질 수 있습니다.

  type = 2의 경우는 "자기자신"과 오른쪽 블록이 함께 떨어져야 하므로 

  블록이 떨어질 수 있는지 확인하는 부분과 블록을 표시하는 부분에 차이가 있습니다.

 

초록색 영역을 기준으로 작성한 drop() 함수를 재활용하기 위해서

파랑색 영역에서 떨어지는 위치, 블록 type을 변경해서 인자로 넘겨줍니다.

즉, 도형 모양과 열 위치만 다를 뿐 6×4 테트리스 두 개를 시뮬레이션 합니다.

    

② 2 ~ 4 행 번호 중 가득 찬 여부 확인 → checkFull()

    가득찬 경우, 해당 행(row)을 지우고 위에 있는 행들을 땡겨옵니다.

- 문제 내용상 연한 색깔 영역인 0 ~ 1행에서는 블록이 한줄 가득차는 경우가 없으므로

   2 ~ 5행 번호만 확인합니다.

※ 블록이 가득한지 확인할 때, 2 → 5순으로 확인하는 것이 효율적입니다.

    (해당 문제나 삼성 A형의 경우 시간초과 제한은 크게 나타나지 않습니다.)

    ex) 아래쪽 행에서 확인하는 경우: 4, 3, 2, 1, 0 행을 아래로 내려옵니다.

          다시 제일 아래행이 되어버린 행 처리를 위해서 4, 3, 2, 1, 0에 있는 행이 내려옵니다.

          하지만 위에서부터 한 경우에는 {3, 2, 1, 0 행 처리} + {4, 3, 2, 1, 0 행 처리}로 횟수적으로 효율적.

      

- 한 행이 가득찬 경우는 Block의 개수가 4개인지 확인합니다.

  한줄이 가득찬 경우(FULL), 점수 득점 & 해당 행을 없애고 위에 있는 줄이 한줄씩 내려옵니다.

기본적으로 위에 있는 행들을 그대로 들고오되, 0번째 행은 블록을 비워주도록 구현

 

③ 연한 색깔 영역에 블록이 남아있는지 확인 → checkLightArea()

    해당 영역에 블록이 존재하는 경우, 제일 아래행을 삭제하고 한 행씩 내려옵니다.

연한 색깔 영역 (0 ~ 1)에 블록이 존재하는 경우

제일 아래 행(5)을 삭제하고, 한 줄씩 내려옵니다. (기존 remove() 함수 활용)

※ 남아 있는 블록의 개수는 모든 블록을 처리한 후 계산

 

※ 디버깅 참고 코드

시뮬레이션 문제이기 때문에 각 함수 혹은 단계별로 디버깅 할 수 있습니다.

- 파랑색 영역을 초록색 영역과 같은 형태로 구현하였기에

  문제에서 보여진 그림처럼 디버깅 하기 위해 오른쪽으로 90° 회전

void printGreen() {
       for (int r = 0; r < 6; ++r) {
              for (int c = 0; c < 4; ++c) {
                     printf("%d ", area[GREEN][r][c]);
              }
              printf("\n");
       }
}
 
void printBlue() {
       int temp[4][6];
       for (int r = 0; r < 6; ++r) {
              for (int c = 0; c < 4; ++c) {
                     temp[4 - c - 1][r] = area[BLUE][r][c];
              }
       }
       for (int r = 0; r < 4; ++r) {
              for (int c = 0; c < 6; ++c) {
                     printf("%d ", temp[r][c]);
              }
              printf("\n");
       }
}

---

#include <stdio.h>
enum {
    EMPTY = 0,
    BLOCK = 1,
    GREEN = 0,
    BLUE = 1,
    FULL = 4,
};
int N, type, x, y, ans;
int area[2][6][4];
void drop(int type, int y, int color) {
    int insert;
    if (type == 1 || type == 3) {
        for (insert = 0; insert < 6; ++insert) {
            if (area[color][insert][y] != EMPTY) break;
        }
        insert--; // 실제 정착되는 행 위치
        area[color][insert][y] = BLOCK;
        if (type == 3) area[color][insert - 1][y] = BLOCK;
    }
    else { // type == 2
        for (insert = 0; insert < 6; ++insert) {
            if (area[color][insert][y] != EMPTY ||
                area[color][insert][y + 1] != EMPTY)
                break;
        }
        insert--;
        area[color][insert][y] = BLOCK;
        area[color][insert][y + 1] = BLOCK;
    }
}
 
void remove(int color, int row) {
    for (int r = row; r >= 0; --r) {
        if (r == 0) {
            for (int c = 0; c < 4; ++c)
                area[color][r][c] = EMPTY;
            return;
        }
        for (int c = 0; c < 4; ++c)
            area[color][r][c] = area[color][r - 1][c];
    }
}
 
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] == BLOCK) 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] == BLOCK) {
                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, y, GREEN);
        if (type == 1) drop(1, 4 - x - 1, BLUE);
        else if (type == 2) drop(3, 4 - x - 1, BLUE);
        else drop(2, 4 - (x + 1) - 1, BLUE);
 
        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] == BLOCK) blockCnt++;
            }
        }
    }
    printf("%d\n", blockCnt);
}