19235번: 모노미노도미노

모노미노도미노는 아래와 같이 생긴 보드에서 진행되는 게임이다. 보드는 빨간색 보드, 파란색 보드, 초록색 보드가 그림과 같이 붙어있는 형태이다. 게임에서 사용하는 좌표 (x, y)에서 x는 행,

www.acmicpc.net

문제

모노미노도미노는 아래와 같이 생긴 보드에서 진행되는 게임이다. 보드는 빨간색 보드, 파란색 보드, 초록색 보드가 그림과 같이 붙어있는 형태이다. 게임에서 사용하는 좌표 (x, y)에서 x는 행, y는 열을 의미한다. 빨간색, 파란색, 초록색 보드가 사용하는 좌표는 그 색으로 그림에 적혀있다.

<그림 1> 모노미노도미노 게임 보드

이 게임에서 사용하는 블록은 타일 하나 또는 두 개가 가로 또는 세로로 붙어있는 형태이다. 아래와 같이 세 종류가 있으며, 왼쪽부터 순서대로 크기가 1×1, 1×2, 2×1 이다.

<그림 2> 모노미노도미노 게임에서 사용하는 블록

블록을 놓을 위치를 빨간색 보드에서 선택하면, 그 위치부터 초록색 보드로 블록이 이동하고, 파란색 보드로 블록이 이동한다. 블록의 이동은 다른 블록을 만나거나 보드의 경계를 만나기 전까지 계속해서 이동한다. 예를 들어, 크기가 1×1인 블록을 (1, 1)에 놓으면, 보드의 상태는 <그림 3>과 같이 변한다.

&lt;그림 3&gt;

여기서 크기가 1×2인 블록을 (3, 0)과 (3, 1)에 놓으면 <그림 4>와 같이 보드의 상태가 변한다.

&lt;그림 4&gt;

다시 이 상태에서 크기가 2×1인 블록을 (2, 2), (3, 2)와 (2, 3), (3, 3)에 놓으면 <그림 5>와 같이 변한다.

&lt;그림 5&gt;

초록색 보드의 4번 행은 모든 칸이 타일로 가득 차있다. 이렇게 초록색 보드에서 어떤 행이 타일로 가득 차 있다면, 그 행의 타일은 모두 사라진다. 사라진 이후에는 초록색 보드에서 각 블록이 다른 블록을 만나거나 경계를 만나기 전까지 아래로 이동한다. 파란색의 경우는 열이 타일로 가득 차 있으면, 그 열의 타일이 모두 사라지며, 사라진 이후에는 파란색 보드에서 각 블록이 다른 블록을 만나거나 경계를 만나기 전까지 오른쪽으로 이동한다. 이렇게 한 행이나 열이 타일로 가득 차서 사라지면 1점을 획득한다. 점수는 사라진 행 또는 열의 수와 같다. 만약, 두 개의 행이 사라지면 2점을 획득하게 되고, 한 행과 한 열이 사라져도 2점을 획득하게 된다. 위의 보드는 아래와 같이 변하고, 1점을 얻는다.

&lt;그림 6&gt;

여기서 크기가 2×1인 블록을 (1, 3), (2, 3)에 놓으면 보드는 <그림 7>과 같이 변한다.

&lt;그림 7&gt;

초록색 보드의 0, 1번 행과 파란색 보드의 0, 1번 열은 그림에는 연한색으로 표현되어 있는 특별한 칸이다. 초록색 보드의 0, 1번 행에 블록이 있으면, 블록이 있는 행의 수만큼 아래 행에 있는 타일이 사라지고, 초록색 보드의 모든 블록이 아래로 경계를 만나기 전까지 이동하고, 파란색 보드의 0, 1번 열에 블록이 있으면, 블록이 있는 열의 수만큼 오른쪽 열에 있는 타일이 사라지고, 파란색 보드의 모든 블록이 오른쪽으로 경계를 만나기 전까지 이동하게 된다. 위의 그림은 파란색 보드의 1번 열에 블록이 있기 때문에, 5번 열에 있는 블록이 모두 사라지고, 파란색 보드의 모든 블록이 오른쪽으로 한 칸 이동하게 된다. 따라서, 보드는 <그림 8>과 같이 변하게 된다.

&lt;그림 8&gt;

위의 보드에서 1×2인 블록을 (0, 0), (0, 1)에 놓으면 <그림 9>와 같다.

&lt;그림 9&gt;

여기서 크기가 2×1인 블록을 (2, 0), (3, 0)에 놓으면 <그림 10>과 같이 변한다. 파란색 보드는 1번 열에 블록이 생겨서 오른쪽으로 한 칸씩 이동한 상태이다.

&lt;그림 10&gt;

크기가 2×1인 블록을 (1, 2), (2, 2)에 놓으면, <그림 11>과 같이 변한다.

&lt;그림 11&gt;

파란색 보드는 1번 열에 블록이 있기 때문에, 5번 열의 타일이 사라지고 모든 블록이 오른쪽으로 한 칸씩 이동하게 된다. 초록색 보드는 4번 행의 모든 칸에 타일이 있기 때문에, 1점을 얻으면서, 4번 행의 모든 타일이 사라진다.

&lt;그림 12&gt;

<그림 12>는 <그림 11>의 상태에서 파란색 보드는 모든 블록이 오른쪽으로 한 칸 이동했고, 초록색 보드의 4번 행이 모두 사라진 상태이다. 이제, 초록색 보드에서 나머지 블록이 아래로 경계나 다른 블록을 만나기 전까지 내려와야 한다. 여기서 다시 <그림 13>과 같이 5번 행의 모든 칸에 타일이 가득차게 된다.

&lt;그림 13&gt;

블록의 이동 때문에, 다시 행이나 열이 타일로 가득차는 경우가 또 발생할 수도 있다. 이 경우에도 1점을 얻고, 그 행이나 열의 모든 타일을 제거하고 다시 나머지 블록을 이동하면 된다. 따라서, <그림 11>의 최종 결과는 <그림 14>가 된다.

&lt;그림 14&gt;

행이나 열이 타일로 가득찬 경우와 연한 칸에 블록이 있는 경우가 동시에 발생할 수 있다. 이 경우에는 행이나 열이 타일로 가득 찬 경우가 없을 때까지 점수를 획득하는 과정이 모두 진행된 후, 연한 칸에 블록이 있는 경우를 처리해야 한다.

블록은 보드에 놓인 이후에 다른 블록과 합쳐지지 않는다. 나누어지는 경우는 행이나 열이 타일로 가득찬 경우에 발생할 수 있다. 초록색 보드에서는 2×1 블록에서 일부가 사라져서 1×1 블록이 될 수 있고, 파란색 보드에서는 1×2 블록에서 일부가 사라져서 1×1 블록이 될 수 있다.

블록을 놓은 위치가 순서대로 주어졌을 때, 얻은 점수와 초록색 보드와 파란색 보드에 타일이 있는 칸의 개수를 모두 구해보자.

입력

첫째 줄에 블록을 놓은 횟수 N(1 ≤ N ≤ 10,000)이 주어진다.

둘째 줄부터 N개의 줄에 블록을 놓은 정보가 한 줄에 하나씩 순서대로 주어지며, t x y와 같은 형태이다.

  • t = 1: 크기가 1×1인 블록을 (x, y)에 놓은 경우
  • t = 2: 크기가 1×2인 블록을 (x, y), (x, y+1)에 놓은 경우
  • t = 3: 크기가 2×1인 블록을 (x, y), (x+1, y)에 놓은 경우

블록이 차지하는 칸이 빨간색 칸의 경계를 넘어가는 경우는 입력으로 주어지지 않는다.

출력

첫째 줄에 블록을 모두 놓았을 때 얻은 점수를 출력한다.

둘째 줄에는 파란색 보드와 초록색 보드에서 타일이 들어있는 칸의 개수를 출력한다.

예제 입력 1

1
1 1 1

예제 출력 1

0
2

<그림 3>과 같다.

예제 입력 2

2
1 1 1
2 3 0

예제 출력 2

0
6

<그림 4>와 같다.

예제 입력 3

4
1 1 1
2 3 0
3 2 2
3 2 3

예제 출력 3

1
10

<그림 6>과 같다.

예제 입력 4

5
1 1 1
2 3 0
3 2 2
3 2 3
3 1 3

예제 출력 4

1
12

<그림 8>과 같다.

예제 입력 5

6
1 1 1
2 3 0
3 2 2
3 2 3
3 1 3
2 0 0

예제 출력 5

1
16

<그림 9>와 같다.

예제 입력 6

7
1 1 1
2 3 0
3 2 2
3 2 3
3 1 3
2 0 0
3 2 0

예제 출력 6

1
18

<그림 10>과 같다.

예제 입력 7

8
1 1 1
2 3 0
3 2 2
3 2 3
3 1 3
2 0 0
3 2 0
3 1 2

예제 출력 7

3
11

알고리즘 분류

  • 구현
  • 시뮬레이션

풀이

문제를 잘못 이해해서 5시간을 써버렸다. 코딩 테스트에 이런 문제가 나오면 어쩌지..

 

10X10 배열을 사용해야할 것 같지만, 그렇게 안 해도 된다.

초록색, 파란색 영역 둘 다 6X4 배열을 사용한다. 어차피 빨간색 격자에는 블록이 쌓이지 않는다고 했기 때문이다.

 

1. 블록이 떨어질 때

블록이 떨어질 때는 타입을 1, 2, 3으로 구분해서, 0행부터 차례대로 X열에 블록이 있는지 없는지 확인하고, 블록이 없는 행까지 블록을 떨어뜨린다. 타입 2인 블록은 X+1열까지 같이 확인해준다.

 

2. 블록의 한 행이 사라질 때

이번엔 격자의 5행부터 2행까지 역순으로, Y행마다 0~3열을 확인해서 0~3열에 전부 블록이 채워져 있다면 없애준 후 점수를 1점 올린다. 한 행이라도 블록이 사라진 곳이 존재한다면 블록들을 끌어내리고, 다시 격자의 5행부터 2행까지 역순으로 탐색해준다. 이 과정에서 재귀를 사용한다.

 

3. 0~1행에 블록이 있을 때

1행에만 블록이 있다면 5행을, 0행까지 블록이 있다면 4행까지 블록을 제거해준다. 여기서 본인은 0~3(4)행까지의 블록을 그대로 2(1)줄씩 내리는 것으로 이해하고 풀었기 때문에 엄청난 시간을 잡아먹었는데, 그게 아니고 5(4)행까지 블록을 제거한 후에도 마찬가지로 블록을 아래로 끌어내리는 것이다. 그리고 다시 2번 과정을 반복한다. 이때부터는 0~1행에 블록이 없을 것이기 때문에, 3번 과정은 한 번만 진행해준다.

 

4. 1~3번 과정을 N번 반복하고, 점수를 출력하고 모든 과정이 끝난 이후 초록색 및 파란색 격자에 남아있는 타일의 수의 합을 출력해준다.

코드

#include <iostream>
#include <string>
#include <cmath>
#include <set>
#include <unordered_map>
#include <stack>
#include <queue>
#include <vector>
#include <algorithm>
#define FIRST cin.tie(NULL); cout.tie(NULL); ios::sync_with_stdio(false);
#define MAX 6
#define MAX_N 10005
#define LL long long
#define INF 1e9

using namespace std;
int N;
int Green_MAP[MAX][MAX];
int Blue_MAP[MAX][MAX];
int answer = 0;

// 블록이 초록색 보드로 떨어진다.
void Green_MAP_Falling(int T, int Y, int X) {
	if (T == 1) { // 1X1 블록은 그대로 떨어진다.
		int H = 0;
		while ((H <= 5) && (Green_MAP[H][X] == 0)) {
			H++;
		};
		H--;
		Green_MAP[H][X] = T;
	}
	else if (T == 2) { // 1X2 블록은 옆 열까지 비어있는지 확인해야 한다.
		int H = 0;
		while ((H <= 5) && (Green_MAP[H][X] == 0) && (Green_MAP[H][X + 1] == 0)) {
			H++;
		};
		H--;
		Green_MAP[H][X] = T;
		Green_MAP[H][X + 1] = T;
	}
	else if (T == 3) { // 2X1 블록은 밑 행까지 비어있는지 확인해야 한다.
		int H = 0;
		while ((H <= 4) && (Green_MAP[H][X] == 0) && (Green_MAP[H + 1][X] == 0)) {
			H++;
		};
		H--;
		Green_MAP[H][X] = T;
		Green_MAP[H + 1][X] = T;
	}
}

void Green_Move() {
	for (int i = 4; i >= 0; i--) { // 4열부터 블록을 내릴 수 있는지 확인한다.
		for (int j = 0; j <= 3; j++) {
			int Number = Green_MAP[i][j]; // 블록의 번호
			if ((Number == 1) || (Number == 3)) { // 블록이 1X1이거나 2X1이면 옆 열까지 따질 필요 없다.
				// 타입 3인 경우에도, 아래 블록을 내린 후 윗 블록을 내리기 전에 다른 블록이 끼어들 일이 없으므로, 하나하나씩 내려줘도 된다.
				if (Green_MAP[i + 1][j] == 0) {
					int H = i + 1;
					while ((H <= 5) && (Green_MAP[H][j] == 0)) {
						H++;
					};
					H--;
					Green_MAP[i][j] = 0;
					Green_MAP[H][j] = Number;
				}
			}
			else if ((j < 3) && (Number == 2)) {
				// 타입 2인 경우, 오른쪽 열의 타일도 현재 타일과 번호가 같아야 한다. 그리고 오른쪽만을 확인하므로, 제일 오른쪽 열인 경우에는 제외한다.
				if (Green_MAP[i][j + 1] == Number) {
					if ((Green_MAP[i + 1][j] == 0) && (Green_MAP[i + 1][j + 1] == 0)) {
						int H = i + 1;
						while ((H <= 5) && (Green_MAP[H][j] == 0) && (Green_MAP[H][j + 1] == 0)) {
							H++;
						}
						H--;
						Green_MAP[i][j] = 0;
						Green_MAP[i][j + 1] = 0;
						Green_MAP[H][j] = 2;
						Green_MAP[H][j + 1] = 2;
					}
				}
			}
		}
	}
}

void Green_Full_Block() {
	// 연한 색을 제외하고, 초록색 보드를 5행부터 역순으로 탐색해주며 행이 가득 차 있다면 블록을 모두 제거해준다.
	bool Flag = true; // Flag가 true라면 더 이상 블록으로 가득 차 없어질 행이 없다는 뜻이다.
	for (int i = 5; i >= 2; i--) {
		bool isFull = true; // i행이 블록으로 가득 차 있으면 true, 아니면 false
		for (int j = 0; j <= 3; j++) {
			if (Green_MAP[i][j] == 0) { // 하나라도 비었다면 i행의 모든 블록을 제거하지 않는다.
				isFull = false;
				break;
			}
		}
		if (isFull) {
			Flag = false;
			answer++; // i행의 블록을 모두 제거했으므로, 점수를 1점 올린다.
			for (int j = 0; j <= 3; j++) { // i행의 블록을 모두 제거
				Green_MAP[i][j] = 0;
			}
		}
	}
	if (!Flag) { 
		/*
			한 행 이상 블록을 제거했다면 블록을 움직여주고, 
			블록을 움직이고 난 후에도 블록을 제거할 행이 있는지 확인해준다.
			이 때 재귀를 사용한다.
		*/
		Green_Move();
		Green_Full_Block();
	}
}

void Green_Delete_Row() {
	int Cnt = 0; // 제거할 행의 개수
	for (int i = 0; i <= 1; i++) {
		for (int j = 0; j <= 3; j++) {
			if (Green_MAP[i][j] > 0) { // i행에 하나라도 블록이 있다면 제거할 행이 하나 늘어난다.
				Cnt++;
				break;
			}
		}
	}
	if (Cnt > 0) {
		for (int i = 5; i > (5 - Cnt); i--) { // 5행부터 최대 4행까지 블록을 제거한다.
			for (int j = 0; j <= 3; j++) {
				Green_MAP[i][j] = 0;
			}
		}
	}
	// 5~4행까지 블록을 제거한 후에는 다시 블록을 움직여주고 블록을 제거할 행이 있는지 확인한다.
	Green_Move();
	Green_Full_Block();
}

int Green_Board_Size() {
	int res = 0;
	for (int i = 0; i <= 5; i++) {
		for (int j = 0; j <= 3; j++) {
			if (Green_MAP[i][j] != 0) {
				res++;
			}
		}
	}

	return res;
}

// 블록이 파란색 보드로 떨어진다.
void Blue_MAP_Falling(int T, int Y, int X) {
	// 1X1인 경우에는 그대로 떨어진다.
	if (T == 1) {
		int H = 0;
		while ((H <= 5) && (Blue_MAP[H][X] == 0)) {
			H++;
		};
		H--;
		Blue_MAP[H][X] = T;
	}
	// 2X1인 경우에는 4행까지 따져준다.
	else if (T == 2) {
		int H = 0;
		while ((H <= 4) && (Blue_MAP[H][X] == 0) && (Blue_MAP[H + 1][X] == 0)) {
			H++;
		};
		H--;
		Blue_MAP[H][X] = T;
		Blue_MAP[H + 1][X] = T;
	}
	// 1X2인 경우에는 다음 열까지 따져준다.
	else if (T == 3) {
		int H = 0;
		while ((H <= 5) && (Blue_MAP[H][X] == 0) && (Blue_MAP[H][X + 1] == 0)) {
			H++;
		};
		H--;
		Blue_MAP[H][X] = T;
		Blue_MAP[H][X + 1] = T;
	}
}

void Blue_Move() {
	for (int i = 4; i >= 0; i--) {
		for (int j = 0; j <= 3; j++) {
			int Number = Blue_MAP[i][j]; // 블록의 번호
			if ((Number == 1) || (Number == 2)) { // 블록이 1X1이거나 2X1이면 옆 열까지 따질 필요 없다.
				// 타입 3인 경우에도, 아래 블록을 내린 후 윗 블록을 내리기 전에 다른 블록이 끼어들 일이 없으므로, 하나하나씩 내려줘도 된다.
				if (Blue_MAP[i + 1][j] == 0) {
					int H = i + 1;
					while ((H <= 5) && (Blue_MAP[H][j] == 0)) {
						H++;
					};
					H--;
					Blue_MAP[i][j] = 0;
					Blue_MAP[H][j] = Number;
				}
			}
			else if ((j < 3) && (Number == 3)) {
				// 타입 3인 경우, 오른쪽 열의 타일도 현재 타일과 번호가 같아야 한다. 그리고 오른쪽만을 확인하므로, 제일 오른쪽 열인 경우에는 제외한다.
				if (Blue_MAP[i][j + 1] == 3) {
					if ((Blue_MAP[i + 1][j] == 0) && (Blue_MAP[i + 1][j + 1] == 0)) {
						int H = i + 1;
						while ((H <= 5) && (Blue_MAP[H][j] == 0) && (Blue_MAP[H][j + 1] == 0)) {
							H++;
						}
						H--;
						Blue_MAP[i][j] = 0;
						Blue_MAP[i][j + 1] = 0;
						Blue_MAP[H][j] = 3;
						Blue_MAP[H][j + 1] = 3;
					}
				}
			}
		}
	}
}

void Blue_Full_Block() {
	// 특정 행이 블록으로 가득 차 있다면 제거해주고, 위에 있는 모든 블록을 아래로 떨군다.
	bool Flag = true; // Flag가 true라면 더 이상 블록으로 가득 차 없어질 행이 없다는 뜻이다.
	for (int i = 5; i >= 2; i--) {
		bool isFull = true; // i행이 블록으로 가득 차 있으면 true, 아니면 false
		for (int j = 0; j <= 3; j++) {
			if (Blue_MAP[i][j] == 0) {
				isFull = false;
				break;
			}
		}
		if (isFull) {
			Flag = false;
			answer++;
			for (int j = 0; j <= 3; j++) { // i행의 블록을 모두 제거
				Blue_MAP[i][j] = 0;
			}
		}
	}
	if (!Flag) {
		Blue_Move();
		Blue_Full_Block();
	}
}

void Blue_Delete_Row() {
	int Cnt = 0; // 제거할 행의 개수
	for (int i = 0; i <= 1; i++) {
		for (int j = 0; j <= 3; j++) {
			if (Blue_MAP[i][j] > 0) {
				Cnt++;
				break;
			}
		}
	}
	if (Cnt > 0) {
		for (int i = 5; i > (5 - Cnt); i--) {
			for (int j = 0; j <= 3; j++) {
				Blue_MAP[i][j] = 0;
			}
		}
	}
	Blue_Move();
	Blue_Full_Block();
}

int Blue_Board_Size() {
	int res = 0;
	for (int i = 0; i <= 5; i++) {
		for (int j = 0; j <= 3; j++) {
			if (Blue_MAP[i][j] != 0) {
				res++;
			}
		}
	}

	return res;
}

int main() {
	FIRST
	cin >> N;
	for (int i = 1; i <= N; i++) {
		int T, Y, X;
		cin >> T >> Y >> X;
		// 블록이 초록색 보드로 떨어진다.
		Green_MAP_Falling(T, Y, X);
		Blue_MAP_Falling(T, X, Y);
		Green_Full_Block();
		Green_Delete_Row();
		Blue_Full_Block();
		Blue_Delete_Row();
	}
	cout << answer << "\n";
	cout << Green_Board_Size() + Blue_Board_Size() << "\n";

	return 0;
}

'BOJ > Platinum ~ Diamond' 카테고리의 다른 글

[BOJ/Platinum 4] 백준 3111 검열(C++)  (0) 2022.01.29
[BOJ/Platinum 4] 백준 12094 2048 (Hard)(C++)  (0) 2022.01.28
[BOJ/Platinum 5] 백준 2642 전개도(C++)  (0) 2022.01.26
[BOJ/Platinum 4] 백준 3025 돌 던지기(C++)  (0) 2022.01.26
[BOJ/Platinum 5] 백준 19541 역학 조사(C++)  (0) 2022.01.25

티스토리툴바