[BOJ]백준 19235번: 모노미노도미노 풀이 및 코드

www.acmicpc.net/problem/19235

19235번: 모노미노도미노

(구)삼성 기출문제집에 있던 문제들 중 단연 난이도 1위를 자랑했던 문제이자

인턴 지원할 때 코테에서 만났던 문제........!!

물론 체감 난이도 자체는 엄~~~~~청 높은 편은 아니었기에 2솔을 할 수 있었다

 

하지만 해당 링크의 문제는 까다로운 조건이 있어서..... 그걸 모두 만족시켜주어야만 솔브 가능하다

이렇게 빨간색 구역 내의 좌표에 블럭을 놓으면, 그걸 아래와 오른쪽으로 모두 내리고 추가 연산을 해줘야 하는데

기존의 2차원 좌표 배열을 3차원으로 늘리고, 좌표도 그에 맞게 회전처리 해주면 된다!!

 

예를 들면 초록색 구역 기준에서는 (3,0)에 2번 블럭을 놓은 것으로 보이지만,

파란색 구역 기준으로 90도 회전해주면 (0,0)에 3번 블럭을 놓은 것으로 보인다

 

민트색 형광펜으로 표시한 것 처럼, 보드 내에 있는 모든 블록은 원래의 블록 형태를 지니고 있기 때문에 중력으로 내려줄 때 고려해야 한다

그래서 보드에 표시할 때에도 현재 블록이 몇번 블록인지, 나와 연결된 블록 좌표는 어디에 있는지 체크해줬다

 

추가적으로 2번 블록이 포함된 행이 pop되었다면, 남아있는 2번 블록은 1번 블록으로 종류를 변경해주는 연산이 필요

#include <cstdio>
#include <vector>
using namespace std;
typedef struct { int r, c; }point;
typedef struct { int k; point p; }block;
block board[2][10][4];

int n, t, x, y, ans,sum;

bool safe(int c, vector<point> p) {
	for (auto x : p)
		if (x.r >= 10 || board[c][x.r][x.c].k)	//비어있지 않다면
			return false;
	return true;
}
void blockMove(int c, point cur, block b) {
	vector<point> v, next;
	v.push_back(cur);
	if (b.k > 1)v.push_back(b.p);

	for (auto x : v) {
		board[c][x.r][x.c] = { 0,{0,0} };
		next.push_back({ x.r + 1,x.c });
	}

	while (safe(c, next)) {
		v = next;
		for (int i = 0; i < next.size(); i++)
			next[i].r++;
	}

	if (b.k == 1) {
		board[c][v[0].r][v[0].c] = { 1,v[0] };
		return;
	}

	for (int i = 0; i < 2; i++) {
		board[c][v[i].r][v[i].c] = { b.k,v[!i] };
	}
}

int fullRow(int c) {
	for (int r = 9; r >= 6; r--) {
		bool b = true;
		for (int i = 0; i < 4; i++)
			if (!board[c][r][i].k)b = 0;
		if(b) return r;
	}
	for (int r = 5; r >= 4; r--) {
		for (int i = 0; i < 4; i++)
			if (board[c][r][i].k)return r;
	}
	return -1;
}
void rowPop(int cl, int row) {
	for (int i = 0; i < 4; i++) {
		int kin = board[cl][row][i].k;
		if (!kin)continue;

		if (kin==3){
			point next = board[cl][row][i].p;
			board[cl][next.r][next.c] = { 1,next };
		}
		board[cl][row][i] = { 0,{0,0} };
	}
	int f = fullRow(cl);
	if(f<6)
	for (int r = row-1; r > 3; r--) {
		for (int i = 0; i < 4; i++)
			if (board[cl][r][i].k)
				blockMove(cl, { r,i }, board[cl][r][i]);
	}
}
int main() {
	scanf("%d", &n);
	while (n--) {
		scanf("%d%d%d", &t, &y, &x);
		//printf("%d %d %d\n", t, y, x);

		for (int B = 0; B < 2; B++) {
			if (t == 1) {
				board[B][y][x] = { 1,{y,x} };
			}
			else if (t == 2) {
				board[B][y][x] = { 2,{y,x + 1} };
				board[B][y][x + 1] = { 2,{y,x} };
			}
			else {
				board[B][y][x] = { 3,{y + 1,x} };
				board[B][y + 1][x] = { 3,{y,x} };
			}

			blockMove(B, { y,x }, board[B][y][x]);

			int state;
			while ((state = fullRow(B)) != -1) {
				if (state > 5) {
					rowPop(B, state);
					ans++;
				}
				else
					rowPop(B, 9);
			}

			int temp = y; y = x; x = 3 - temp;
			if (t == 2)t = 3;
			else if (t == 3) { t = 2; x--; };
		}
		//print();
	}
	for (int k = 0; k < 2; k++)
		for (int i = 4; i < 10; i++)
			for (int j = 0; j < 4; j++)
				if (board[k][i][j].k)sum++;
	printf("%d\n%d", ans, sum);
	return 0;
}

조금 까다로웠던 문제지만 설계를 잘 한다면 문제없이 풀 수 있을 것 같다~~🤗