[BOJ 3019] 테트리스

#문제

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

#풀이

저의 머리가 역시 안좋구나...하게 만든 문제입니다.

처음 풀이 방법은 맵을 직접 2차원 배열에 넣고, 그 안에서 주어진 블럭을 계속해서 만들어 확인하는 방법이었습니다.

이렇게 할 경우, 블럭마다 그리는 방법이 전부 다르기 때문에 일일이 만들어줘야하며, 

이차원 배열에 계속 그렸다 확인하고 지우고, 다시 그리고 지우고를 반복하는 상황이 만들어졌습니다..

뭔가 아니다 싶어서 검색한 결과 세상 똑똑하신 분들이 많구나하는 생각을 하게 되었습니다..

일단 방법은 이러합니다.

먼저 쌓으려는 블럭의 밑바닥의 높이를 알아합니다.

여기서 밑바닥은 아래 그림과 같은 것을 의미합니다.

위 그림과 같이 빨간 선이 있는 부분이 밑바닥입니다.

여기서 왜!? 왜 저 부분이 필요한거야? 

어느정도 감이 오시는분은 정말 똑똑하신 겁니다..

바로 저 부분이 주어진 맵과 맞닿아야 

"블록이 떨어졌을 때, 블록과 블록 또는 블록과 바닥 사이에 채워져있지 않은 칸이 생기면 안된다." 

라는 조건이 만족하기 때문이죠. 

따라서 위 그림의 높이는 각각 열에 "01"을 의미합니다.

그렇다면 이제 이 블럭이 맵과 맞닿았는지 어떻게 확인을 할까요?

예시로 문제에서 주어진 입력을 보도록 하겠습니다.

위 블록을 주어진 입력에 넣었을때, 위와 같은 빈칸이 생기게 됩니다.

처음에 "저 맵의 높이만큼 더해주고 맵과 차이가 0이면 고를 수 있겠네!" 라는 생각을 하게 되었습니다.

제 생각대로라면 위 그림과 같이 노란색 블럭에 경우, 2(1열)와 2(2열) = 1(맵 2번째 열 높이) + 1(원래 블럭의 밑바닥)가 됩니다.

음...뭔가 이상하죠...?

실제로는 2열의 맵 높이와 상관없이, 1열에서 무조건 오른쪽 위에 사각형이 있어야하기 때문에 실제 2열의 높이는 3이 되어야 합니다.

오류가 생겼습니다... 정말.. 단순하게 생각하는것 같네요..:(

다시한번 블럭과 맵을 잘 봅시다. 흐음....

오! 1열에서 2열로 넘어갈때의 높이의 변화량이 보이십니까?

블록의 경우 0 -> 1로 상승하고 맵의 경우 2 -> 1로 하강하게 됩니다.

따라서, 변화량은 블럭: 1-0 = 1, 맵: 1 - 2 = -1 이므로 2열에서 2칸의 차이가 생기게 되는것입니다.

찾았습니다!

이번에는 맞는 블럭을 볼까요?

위 블록은 ㅓ 모양이므로 밑바닥의 높이는 "10" 됩니다.

블럭의 변화량은 0-1 = -1, 맵의 변화량은 1-2 = -1이 되어 빈칸이 존재하지 않습니다.

만약 너비가 3, ㅜ 와 같은 모양은 두번의 변화량을 비교하면 되겠죠? :)

이 블록도 2~3열 변화량에서 차이가 생기네요!

드디어 찾았습니다...

다음으로는 블럭들을 한칸씩 이동시키며 확인을 해봐야 됩니다.

이때, 혹시나 조심해야 할 것은 "블록이 필드를 벗어나지 않으면 된다." 이란 조건입니다.

모두 왼쪽이 기준이므로 끝 = (전체 열 - 블럭의 너비) 까지만 체크하면 됩니다.

나머지 블럭들 1~7번까지 위에 방법과 똑같이 해주시면 됩니다.

#코드

#include <iostream>
#include <vector>
using namespace std;
 
int C,P;
//C, 즉 열의 최대 크기가 100이므로 0~99까지의 배열을 만들어준다.
int map[100];
 
//쌓기 가능한지 알아보는 함수는 해당 블럭의 밑바닥을 인자로 받아 수행한다.
int numOfStackable(string block){
    //쌓기 가능한지 알아보기 위해서는 쌓는 부분 즉, 블럭의 넓이만 확인하면 된다.
    //너비를 알아내기 위해서는 string형이 int형보다는 편하기 때문에 string 사용.
    int len = (int)block.size();
    vector<int> blockHeight;
    for(int i = 0; i < len; i++){
        blockHeight.push_back(block[i] - '0');
    }
    int cnt = 0;
    //왼쪽에서부터 확인할 것이며 블럭이 넘어가면 안되므로 |C -블럭 너비| 까지만 진행
    for(int i = 0; i <= C - len; i++){
        bool possible = true;
        for(int j = 1; j < len; j++){
            //변화량 확인
            if(blockHeight[j] - blockHeight[j-1] != map[i+j] - map[i+j-1]){
                possible = false;
                break;
            }
        }
        if(possible){
            cnt++;
            possible = true;
        }
    }
    return cnt;
}
 
//테트리스가 놓였을때, 밑바닥과 사이에 틈이 존재하는지 알기위해서는
//테트리스의 밑부분이 어떠한 높이를 가지고 있는지 확인만 하면된다.
//따라서 테트리스들을 모두 표현할 필요가 없으며, 테트리스들의 너비별로의 높이만 저장할 수 있도록 한다.
//예)   ㅗ는 밑 부분의 높이들이 다 0이므로 '000'으로 나타낼 수 있다.
//      ㅏ = '01' , ㅓ = '10' , ㅜ = '101'로 표현 가능
int checkingBuildTetris(int kind){
    int ans = 0;
    if(kind == 1){
        ans += numOfStackable("0");
        ans += numOfStackable("0000");
    }else if(kind == 2){
        ans += numOfStackable("00");
    }else if(kind == 3){
        ans += numOfStackable("001");
        ans += numOfStackable("10");
    }else if(kind == 4){
        ans += numOfStackable("100");
        ans += numOfStackable("01");
    }else if(kind == 5){
        ans += numOfStackable("000");
        ans += numOfStackable("01");
        ans += numOfStackable("10");
        ans += numOfStackable("101");
    }else if(kind == 6){
        ans += numOfStackable("000");
        ans += numOfStackable("20");
        ans += numOfStackable("011");
        ans += numOfStackable("00");
    }else{
        ans += numOfStackable("000");
        ans += numOfStackable("00");
        ans += numOfStackable("110");
        ans += numOfStackable("02");
    }
    return ans;
}
 
int main(){
    cin >> C >> P;
    for(int i = 0; i < C; i++){
        cin >> map[i];
    }
    cout << checkingBuildTetris(P) << endl;
    return 0;
}