[C/C++] 백준 - 3019번 : 테트리스

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

3019번: 테트리스

문제

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

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

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

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

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

 

개인적으로 로직 자체는 구현 문제라 어려움보다는 까다로움이 큰 문제라고 생각한다. 문제의 난이도가 어렵진 않지만 구현자체가 쉽지 않다고 느껴진 문제

 

< 문제 접근 >

각 도형 모양에 맞게 위에서부터 아래로 도형을 내렸졌을 때 블록과 블록 또는 블록과 바닥 사이에 여백이 존재하지 않는 경우의 수를 구하는 문제.

 

처음에 어떻게 구현을 할까 고민했지만 역시 별다른 좋은 방법이 떠오르지 않아 모든 경우의 수(도형의 회전까지 고려)를 확인하여 조건에 부합하는지 확인하는 방식으로 하였다.

 

도형의 모양은 좌표를 이용하여 구현하였고, 가장 왼쪽이면서 가장 아래쪽을 시작 좌표(0,0)으로 생각하는 방식으로 좌표를 작성해주었다. 그리고 초기 조건으로 각 칸의 높이가 주어지기에 높이 바로 위 좌표를 시작 좌표로 생각하여 시작 좌표들을 큐에 넣어주었고 solution함수를 실행하게 되면 큐에서 시작 좌표를 하나씩 꺼내준다. 시작 좌표를 기준으로 각 도형을 회전시켰을 때 다른 모양이 되는 경우까지 모두 회전시켜본 후 조건에 부합하는 지 확인해보았다.

 

#include <iostream>
#include <queue>
#include <vector>
#include <stack>
#include <string>
#include <cstring>
#include <sstream>
#include <set>
#include <unordered_set>
#include <map> 
#include <algorithm>
#include <cmath>
#include <ctime>
#define fastio ios::sync_with_stdio(false), cin.tie(0), cout.tie(0)
#define ENDL cout << endl
#define ll long long
#define ull unsigned long long
#define INF 987654321
#define Mod 1000000009
#define endl '\n'
#define pil pair<int,int>x	

using namespace std;

int C, P;
int board[201][101];

const int cnt_Of_type[7] = { 2, 1, 2, 2, 4, 4, 4 };
const int coverType[7][4][4][2] = {
	{
		{{0, 0}, {-1,0}, {-2,0}, {-3,0}},
		{{0,0,}, {0,1}, {0,2}, {0,3}}
	},

	{
		{{0,0}, {-1,0}, {-1,1}, {0,1}}
	},

	{
		{{0,0}, {0,1}, {-1,1}, {-1,2}},
		{{0,0}, {-1,0}, {0,1}, {1,1}}
	},

	{
		{{0,0}, {0,1}, {1,1}, {1,2}},
		{{0,0}, {-1,0}, {-1,1}, {-2,1}}
	},

	{
		{{0,0}, {0,1}, {0,2}, {-1,1}},
		{{0,0}, {-1,0}, {-2,0}, {-1,1}},
		{{0,0}, {0,1}, {-1,1}, {1,1}},
		{{0,0}, {0,1}, {0,2}, {1,1}}
	},

	{
		{{0,0}, {0,1}, {0,2}, {-1,2}},
		{{0,0}, {-1,0}, {-2,0}, {0,1}},
		{{0,0}, {-1,0}, {-1,1}, {-1,2}},
		{{0,0}, {0,1}, {1,1}, {2,1}}
	},

	{
		{{0,0}, {-1,0}, {0,1}, {0,2}},
		{{0,0}, {-1,0}, {-2,0}, {-2,1}},
		{{0,0}, {0,1}, {0,2}, {1,2}},
		{{0,0}, {0,1}, {-1,1}, {-2,1}}
	}
};

bool isValid(int y, int x) {
	if (board[y][x] == 0) {
		if (1<= y && y <= 200 && 1 <= x && x <= C) 
			return true;
	}
	return false;
}

int isCnt(vector<pair<int, int>>& v) {
	for (auto& ps : v) {
		for (int i = ps.first; i <= 200; i++) {
			if (board[i][ps.second] == 0) return 0;
		}
	}
	return 1;
}

queue<pair<int,int>> input() {
	cin >> C >> P;
	queue<pair<int, int>> q;
	for (int i = 1; i <= C; i++) {
		int x; cin >> x;
		for (int j = 200-x+1; j <= 200; j++) board[j][i] = 1;
		q.push({ 200 - x, i });
	}
	return q;
}

void solution(queue<pair<int,int>> &q) {
	int cnt = 0;
	while (!q.empty()) {
		pair<int, int> cur = q.front();
		q.pop();
		
		for (int i = 0; i < cnt_Of_type[P - 1]; i++) {
			vector<pair<int, int>> v;
			for (int j = 0; j < 4; j++) {
				int ny = cur.first + coverType[P - 1][i][j][0];
				int nx = cur.second + coverType[P - 1][i][j][1];

				if (!isValid(ny, nx)) break;
				v.push_back({ ny, nx });
			}
			if (v.size() == 4) {
				for (auto& ps : v) board[ps.first][ps.second] = 1;
				cnt += isCnt(v);
				for (auto& ps : v) board[ps.first][ps.second] = 0;
			}
			v.clear();
		}
	}
	cout << cnt << endl;
}

int main() {
	fastio;
	queue<pair<int,int>> q = input();
	solution(q);

	return 0;
}