BOJ 3019

18 Mar 2020 • ProblemSolving

테트리스

문제출처

문제 해석

  • 테트리스 게임에서 나오는 블록중 하나가 필드에 떨어질 수 있는 경우의 수를 구하는 문제입니다.
  • 블록은 회전이 가능하고 좌,우로 이동이 가능합니다.
  • 이때, 블록과 블록 사이 또는 블록과 바닥 사이에 채워져있지 않은 칸이 생기면 안됩니다.

설계(20)

  • 시간복잡도 여유가 있어, 구현만 제대로 하면 되는 문제입니다.
  • 먼저, 7가지의 블록이 나올 수 있는 모든 경우를 벡터에 저장합니다. 이때, 모든 블록은 왼쪽 끝을 기준으로 설정하였습니다.
  • 주어지는 높이에 따라 맵을 아래에서부터 지정된 높이까지 1로 생성합니다.
  • 각 열에서 확인해볼 행의 개수는 많아야 4개이므로 해당 높이-4까지 가능한 경우의 수를 카운트 합니다.
  • 벡터에 저장된 블록의 offset좌표를 따라서 매핑을 한 후, 각 블록아래가 바닥 또는 블록인지 구분하여 만약 조건에 맞다면 카운트 하도록 합니다.

구현(40)

코드
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
#define MAXN 105
typedef pair<int,int> P;
vector<vector<P>> block[7]={ { {P(0,0),P(1,0),P(2,0),P(3,0)},{P(0,0),P(0,1),P(0,2),P(0,3)} },
{ {P(0,0),P(0,1),P(1,0),P(1,1)} },
{ {P(0,1),P(0,2),P(1,0),P(1,1)}, {P(0,0),P(1,0),P(1,1),P(2,1)} },
{ {P(0,0),P(0,1),P(1,1),P(1,2)}, {P(0,1),P(1,0),P(1,1),P(2,0)} },
{ {P(0,1),P(1,0),P(1,1),P(1,2)}, {P(0,1),P(1,0),P(1,1),P(2,1)}, {P(0,0),P(0,1),P(0,2),P(1,1)}, {P(0,0),P(1,0),P(1,1),P(2,0)} },
{ {P(0,2),P(1,0),P(1,1),P(1,2)}, {P(0,0),P(1,0),P(2,0),P(2,1)}, {P(0,0),P(0,1),P(0,2),P(1,0)},{P(0,0),P(0,1),P(1,1),P(2,1)} },
{ {P(0,0),P(1,0),P(1,1),P(1,2)}, {P(0,0),P(0,1),P(1,0),P(2,0)}, {P(0,0),P(0,1),P(0,2),P(1,2)} , {P(0,1),P(1,1),P(2,0),P(2,1)} } } ;

int map[MAXN][MAXN];
int height[MAXN];
int C,num;
int ans;
bool is_range(int x, int y, vector<P> v){
    for (int i = 0; i < 4; i++){
        int nx = x + v[i].first;
        int ny = y + v[i].second;
        if (ny < 0 || nx >= MAXN || ny >= C || map[nx][ny]) return false;
    }
    return true;
}
int Check(int x, int y, vector<vector<P> > & v){
    int sum = 0;
    // 회전 종류
    for (int i = 0; i < v.size(); i++){
        if (!(is_range(x,y,v[i]))) continue;
        for (int j = 0; j<  v[i].size(); j++){
            int nx = x + v[i][j].first;
            int ny = y + v[i][j].second;
            map[nx][ny] = 1;
        }
        bool flag = false;
        for (int j = 0;j < v[i].size() && !flag; j++){
            int nx = x + v[i][j].first+1;
            int ny = y + v[i][j].second;
            if (nx < MAXN && !map[nx][ny]) flag = true;
        }
        sum += !flag;
        for (int j = 0; j<  v[i].size(); j++){
            int nx = x + v[i][j].first;
            int ny = y + v[i][j].second;
            map[nx][ny] = 0;
        }
    }
    return sum;
}
int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    cin >> C >> num;
    num--;
    for (int i = 0 ;i < C; i++){
        int tmp;
        cin >> tmp;
        height[i] = tmp;
        while (tmp--){
            map[MAXN-tmp-1][i] = 1;
        }
    }
    for (int j = 0;j < C; j++){
        for (int i = MAXN -1 -height[j]; i>=MAXN-6-height[j]; i--){
            if (map[i][j]) continue;
            ans += Check(i,j,block[num]);
        }
    }
    cout << ans <<"\n";
    return 0;
}
디버깅
  • 실수한 부분이 있습니다.
  • 지문 중 “필드의 행의 수는 무한하다”이라고 언급이 되어있었는데 이를 확인하지 못했습니다.
  • 그래서, 최대 행의 수를 100으로 제한하여 구현하였습니다.
  • 위의 조건을 만족시키기 위하여 최대 높이를 105로 설정하였습니다.
제출결과
  • 0ms

마무리

  • 테트리스 게임의 블록을 이용한 구현문제였습니다. 블록을 구성하는데 더 오래걸렸던 문제입니다.
 BOJ

Related Posts