[DFS] 3019번 테트리스

3019번 테트리스

 

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

 

문제

테트리스는 C열 필드위에서 플레이하는 유명한 게임이다. 필드의 행의 수는 무한하다. 한 번 움직일 때, 아래와 같은 일곱가지 블록 중 하나를 필드에 떨어뜨릴 수 있다.

블록을 떨어뜨리기 전에, 플레이어는 블록을 90, 180, 270도 회전시키거나 좌우로 움직일 수 있다. 이때, 블록이 필드를 벗어나지 않으면 된다. 블록을 필드의 바닥이나 이미 채워져있는 칸의 위에 놓여지게 된다.

창영이가 하고있는 테트리스는 일반적인 테트리스와 약간 규칙이 다르다. 블록이 떨어졌을 때, 블록과 블록 또는 블록과 바닥 사이에 채워져있지 않은 칸이 생기면 안된다.

예를 들어, 아래와 같이 각 칸의 높이가 2, 1, 1, 1, 0, 1인 경우를 생각해보자. 블록 5번을 떨어뜨리는 방법의 수는 아래와 같이 다섯가지이다.

테트리스 필드의 각 칸의 높이와 떨어뜨려야 하는 블록의 번호가 주어진다. 이때, 블록을 놓는 서로 다른 방법의 수를 구하는 프로그램을 작성하시오.

 

입력

첫째 줄에 C와 떨어뜨리는 블록의 번호 P가 주어진다. (1 ≤ C ≤ 100, 1 ≤ P ≤ 7)

둘째 줄에는 각 칸의 높이가 주어진다. 높이는 0보다 크거나 같고, 100보다 작거나 같은 자연수이다.

 

출력

첫째 줄에 블록을 떨어뜨리는 방법의 수를 출력한다.

 

예제 입력

6 5
2 1 1 1 0 1

11 1
0 0 0 100 0 0 0 100 0 0 0

 

예제 출력

5

11

 

해결방법

DFS + 백트래킹으로 모든 경우를 탐색하는 부르트포스 문제이다

 

 

⭐️ 솔루션 ⭐️

전체 노드에 대해 (105x100) 특정 블럭의 4가지 방향에 대해 탐색을 수행한다

또한 테트리스를 설치한 뒤, 밑에 공간을 탐색하는데 최대 4*100 의 시간이 발생한다

따라서 105 * 100 * 4 * 4 * 100 = 16,800,000 이므로 시간 초과가 발생하지 않는다 !!

 

전체적인 흐름은 아래와 같다

1. 한 노드에서 시작해 블럭 4개를 사용하여 테트리스를 설치할 수 있는 4차원 배열을 준비한다
2. 전체 노드에 대해 4방향 탐색을 수행한다
3. 테트리스 설치는 미리 준비한 4차원 배열을 통해 DFS 탐색으로 수행한다
4. 만약 테트리스가 무사하게 설치가 되었다면 테트리스 4블럭의 밑의 좌표들을 검사하여 빈공간 유무를 확인한다

 

테트리스 문제만 나오면 미리 4차원 배열을 만들고 시작하는데 더 간단한 방법이 아마 존재할거같다...

나중에 꼭...! 다시 풀어봐야겠다

 

 

 

소스코드

#include <iostream>
#include <stdio.h>
#include <math.h>
#include <cstring>
#include <vector>
#include <algorithm>
#define MAX 105
#define INF 987654321
using namespace std;
typedef pair<int, int> node;

int col,type,height,ans;
int map[MAX][100];
vector<node> v;

int make[8][4][4][2] = {
    // 0번 블럭 X
    { },
    // 1번 블럭
    {
        // 첫번째 방향
        { {0,0},{0,1},{0,2},{0,3} },
        // 두번째 방향
        { {0,0},{1,0},{2,0},{3,0} },
        // 세번째 방향 (X)
        { {0,0},{0,0},{0,0},{0,0} },
        // 네번째 방향 (X)
        { {0,0},{0,0},{0,0},{0,0} }
    },
    // 2번 블럭
    {
        // 첫번째 방향
        { {0,0},{0,1},{1,0},{1,1} },
        // 두번째 방향 (X)
        { {0,0},{0,0},{0,0},{0,0} },
        // 세번째 방향 (X)
        { {0,0},{0,0},{0,0},{0,0} },
        // 네번째 방향 (X)
        { {0,0},{0,0},{0,0},{0,0} }
    },
    // 3번 블럭
    {
        // 첫번째 방향
        { {0,0},{1,0},{1,1},{2,1} },
        // 두번째 방향
        { {0,0},{0,1},{-1,1},{-1,2} },
        // 세번째 방향 (X)
        { {0,0},{0,0},{0,0},{0,0} },
        // 네번째 방향 (X)
        { {0,0},{0,0},{0,0},{0,0} }
    },
    // 4번 블럭
    {
        // 첫번째 방향
        { {0,0},{1,0},{1,-1},{2,-1} },
        // 두번째 방향
        { {0,0},{0,1},{1,1},{1,2} },
        // 세번째 방향 (X)
        { {0,0},{0,0},{0,0},{0,0} },
        // 네번째 방향 (X)
        { {0,0},{0,0},{0,0},{0,0} }
    },
    // 5번 블럭
    {
        // 첫번째 방향
        { {0,0},{0,-1},{0,1},{-1,0} },
        // 두번째 방향
        { {0,0},{-1,0},{1,0},{0,1} },
        // 세번째 방향
        { {0,0},{0,-1},{0,1},{1,0} },
        // 네번째 방향
        { {0,0},{-1,0},{1,0},{0,-1} }
    },
    // 6번 블럭
    {
        // 첫번째 방향
        { {0,0},{1,0},{2,0},{2,1} },
        // 두번째 방향
        { {0,0},{0,1},{0,2},{1,0} },
        // 세번째 방향
        { {0,0},{0,1},{1,1},{2,1} },
        // 네번째 방향
        { {0,0},{0,1},{0,2},{-1,2} }
    },
    // 7번 블럭
    {
        // 첫번째 방향
        { {0,0},{0,1},{-1,1},{-2,1} },
        // 두번째 방향
        { {0,0},{1,0},{1,1},{1,2} },
        // 세번째 방향
        { {0,0},{0,1},{1,0},{2,0} },
        // 네번째 방향
        { {0,0},{0,1},{0,2},{1,2} }
    },
};

// 밑에 빈공간이 있는지 확인하는 메소드
bool is_ok(int x,int y){
    for(int nx=x; nx<MAX; nx++){
        if(map[nx][y] == 0){
            return false;
        }
    }
    return true;
}

// 1x1 블럭을 4개 설치하기 위한 DFS 탐색
void dfs(int r,int c,int dir,int cnt){
    // 테트리스를 놓은 경우
    if(cnt == 4){
        bool flag = true;
        for(int i=0; i<v.size(); i++){
            int x = v[i].first;
            int y = v[i].second;
            
            if(!is_ok(x,y)){
                flag = false;
                break;
            }
        }
        
        // 밑에 빈공간이 없다면
        if(flag) ans++;
        
        return;
    }
    
    // 다음 테트리스를 놓을 좌표
    int nx = r + make[type][dir][cnt][0];
    int ny = c + make[type][dir][cnt][1];
    
    // 맵을 벗어나거나 테트리스를 놓을 수 없는 곳이라면
    if(nx<0 || ny<0 || nx>=MAX || ny>=col) return;
    if(map[nx][ny] == 1) return;
    
    // 백트래킹
    v.push_back(node(nx,ny));
    map[nx][ny] = 2;
    dfs(r,c,dir,cnt+1);
    map[nx][ny] = 0;
    v.pop_back();
}

int main(int argc, const char * argv[]) {
    // cin,cout 속도향상
    ios_base::sync_with_stdio(false);
    cin.tie(NULL); cout.tie(NULL);
    
    cin >> col >> type;
    
    for(int j=0; j<col; j++){
        cin >> height;
        
        for(int i=MAX-height; i<MAX; i++){
            map[i][j] = 1;
        }
    }
    
    ans = 0;
    
    // 최대 105x100 배열에 대해 모든 칸을 탐색함
    for(int i=0; i<MAX; i++){
        for(int j=0; j<col; j++){
            if(map[i][j] == 1) continue;
            
            for(int d=0; d<4; d++){
                if(type==1 && d>1) break;
                if(type==2 && d>0) break;
                if(type==3 && d>1) break;
                if(type==4 && d>1) break;
                
                dfs(i,j,d,0);
            }
        }
    }
    
    cout << ans << "\n";
    
    return 0;
}