문제
테트리스 비슷한 게임을 구현하는 문제이다. 대신 한 칸짜리 모노미노와 두 칸짜리 도미노를 사용한다. 또, 초록색 보드와 파란색 보드가 있어서 한 입력에 대해서 초록색 보드는 위에서 아래로 떨어지고, 파란색 보드는 왼쪽에서 오른쪽으로 도형이 떨어진다. 초록색 보드는 행이 꽉 차면 테트리스처럼 그 행이 지워지고, 파란색 보드는 열이 꽉 차면 지워진다. 지워질때는 점수를 1점 얻는다. 테트리스 게임은 맨 위까지 도형이 차면 게임 오버인데, 이 게임은 그 대신 가장 위 두 줄에 도형이 있으면 가장 아래줄(파란색 보드는 가장 오른쪽 줄)을 지우는 것으로 대신한다. 주어진 입력대로 도형을 배치했을 때, 얻는 점수와 남은 도형 개수를 구하는 문제이다.
접근
규칙만 잘 따라간다면 그렇게 어렵지 않은 구현 문제이다. 일단 처음 고민해야 할 것은 파란색 보드와 초록색 보드를 어떻게 구현할 것인가이다. 그냥 각각 함수를 따로 구현해 사용할 수도 있겠지만, 그보다는 초록색 보드만 구현하고 이를 재사용하면 편리하다. 초록색 보드에서 $(t,x,y)$인 경우,
- $t=1$일때는 파란색 보드의 $(1, y, 3-x)$
- $t=2$일때는 파란색 보드의 $(3, y, 3-x)$
- $t=3$일때는 파란색 보드의 $(2, y, 2-x)$
에 대응되게 된다. 따라서 그냥 초록색 보드만 구현해 주고, 한 보드에는 위 규칙에따라 변환한 입력을 먹여주면 된다.
그 다음은 각 $t$에 대해 경우를 나누어 구현해주면 된다. 먼저 미노/도미노가 위에서 떨어진다면 어디에 쌓이는지 찾아주고, 그러고 나면 한 줄이 차면 비우는 것, 비운 다음 한 줄씩 내리는 것, 만약 가장 위 두 줄에 하나라도 점유된 칸이 있으면 아래 줄을 비우도록 하는 것을 차근차근 구현하면 된다. 어떤 줄이 차있는지 확인하는 것과 한 줄을 비우는 것은 자주 나오니 함수로 따로 짜면 간결해진다.
주의할 점
입력의 형태가 $2 \times 1$ 도미노 $(t=3)$일때를 주의하자. 초록색 보드에서 기준점은 세로 도미노의 위칸으로 들어오지만, 이는 파란색 보드에서 가로 도미노의 오른쪽 칸이다. 그래서 $(3, x, y)$에는 $(2, y, 2-x)$가 대응되어야 한다.
세로 도미노의 경우, 동시에 두 줄이 지워질 수도 있으니 주의하자. 아랫 줄만 두번 체크한다면, 윗 줄만 지워지는 경우에 틀리게 된다. 아랫 줄을 체크하고 윗줄을 체크하면, 반대로 두 줄 다 지워지는 경우에 틀리게 된다. 이를 해결하려면 윗 줄 먼저 체크하고, 그다음 아랫 줄 체크하면 된다.
Code
링크#include <algorithm>
#include <deque>
#include <iostream>
#include <vector>
using namespace std;
int N;
int green[6][4] = {0};
int blue[6][4] = {0};
// delete a row and move all upper rows downward.
void burst_row(int arr[][4], int row) {
for (int i = 0; row - i - 1 >= 0; i++) {
for (int j = 0; j < 4; j++) {
arr[row - i][j] = arr[row - i - 1][j];
}
}
for (int j = 0; j < 4; j++) {
arr[0][j] = 0;
}
}
// check if a row is full and delete it.
int check_and_burst(int arr[][4], int row) {
int ret = 0;
bool check_burst = true;
for (int i = 0; i < 4; i++) {
if (arr[row][i] == 0) {
check_burst = false;
break;
}
}
if (check_burst) {
// add point
ret++;
burst_row(arr, row);
}
return ret;
}
// debug function
void print_minos() {
cout << "green" << '\n';
for (int i = 0; i < 6; i++) {
for (int j = 0; j < 4; j++) {
cout << green[i][j] << ' ';
}
cout << '\n';
}
cout << "blue" << '\n';
for (int i = 0; i < 6; i++) {
for (int j = 0; j < 4; j++) {
cout << blue[i][j] << ' ';
}
cout << '\n';
}
}
int put_mino(int arr[][4], int t, int x, int y) {
int row = 0;
int ret = 0;
if (t == 1) {
while (arr[row][y] == 0 && row < 6) {
row++;
}
arr[--row][y] = 1;
ret += check_and_burst(arr, row);
// check special cells
for (int j = 0; j < 4; j++) {
if (arr[1][j] == 1) {
burst_row(arr, 5);
break;
}
}
} else if (t == 2) {
// find available position
while (arr[row][y] == 0 && arr[row][y + 1] == 0 && row < 6) {
row++;
}
row--;
arr[row][y] = 1;
arr[row][y + 1] = 1;
ret += check_and_burst(arr, row);
// special cells
for (int j = 0; j < 4; j++) {
if (arr[1][j] == 1) {
burst_row(arr, 5);
break;
}
}
} else { // t== 3
// find available position
while (arr[row + 1][y] == 0 && row + 1 < 6) {
row++;
}
row--;
arr[row][y] = 1;
arr[row + 1][y] = 1;
// check line burst
ret += check_and_burst(arr, row); // upper
ret += check_and_burst(arr, row + 1); // lower
// special cells
// do it twice.
for (int foo = 0; foo < 2; foo++) {
for (int j = 0; j < 4; j++) {
if (arr[1][j] == 1) {
burst_row(arr, 5);
break;
}
}
}
}
return ret;
}
int main() {
ios::sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);
// get input
cin >> N;
int ans = 0;
while (N--) {
int t, x, y;
cin >> t >> x >> y;
ans += put_mino(green, t, x, y);
if (t == 1) {
ans += put_mino(blue, 1, y, 3 - x);
} else if (t == 2) {
ans += put_mino(blue, 3, y, 3 - x);
} else {
ans += put_mino(blue, 2, y, 2 - x);
}
// print_minos();
}
int num = 0;
for (int i = 2; i < 6; i++) {
for (int j = 0; j < 4; j++) {
num += green[i][j];
num += blue[i][j];
}
}
cout << ans << '\n'
<< num;
return 0;
}
여담
- 2차원 배열을 함수의 파라미터로 넘기는 법을 이번 기회에 알아보게 되었다. 여기를 참고했으며, fixed size array일 때는 그냥
int arr[][42]와 같이 넘기면 된다.
