[백준] 20061번: 모노미노도미노2

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

20061번: 모노미노도미노 2

나머지 예제 생략

 

 

문제 이해

그냥 시뮬레이션을 돌리면 되는 문제이다.

 

처음에 저 맵을 그대로 만들어야 하나...? 했는데, 그냥 초록맵과 파랑맵을 만들어줬다.

빨간맵의 (y, x)에 블럭이 들어왔을 때, 파랑맵에는 y행에서 들어갈 수 있는 위치를 찾고 초록 맵에는 x열에 들어갈 수 있는 위치를 찾는다.

 

초록맵과 파랑맵에 고통으로 들어갈 수 있는 함수를 만드려고 했다가 너무 복잡해져서 그냥 따로 다 구현했다. 

초록맵이나 파랑맵이나 구현 방식은 거의 비슷하므로 초록맵을 기준으로 설명을 해보자면

 

Put_On_Map_G()

(y, x)위치에 t모양의 블럭을 넣는다.

• 블럭을 넣고 (Find_And_Put_G())
• 만약에 한 줄(가로)가 채워져있으면 그 줄을 지우고 맵을 밑으로 내리고, 다시 채워진 가로 줄이 있는지 확인하고 지우고 내리는 작업을 반복한다. 만약 채워진 가로 줄이 없으면 다음 단계로 넘어간다. (Earn_Point_G())
• 만약 튀어나온 부분이 있으면 그 만큼 맵을 아래로 내려준다. (Map_Overflow_G())

Find_And_Put_G()

• t == 1일 때는 한 칸이니까 딱히 어디에 걸릴 것도 없어서 1행부터 아래로 내려가면서 가장 아래인 곳에 넣어준다
• t == 2일 때는 가로로 긴 모양이라서 1행부터 아래로 내려가면서 그 블럭이 못들어가는 행을 만났을 때 ((r, c) != 0 || (r, c+1) != 0)그 전 행에 넣어준다.
• t == 3일 떄는 세로로 긴 모양이라서 1행부터 아래로 내려가면서 그 불럭이 못들어가는 행을 만났을 때 ((r+1, c) != 0)일때 그 전 행에 넣어준다.

  void Find_And_Put_G(int t, int y, int x) {
  	int r =y, c = x;
  	if (t == 1) {
  		// 하나의 위치만 찾으면 됨
  		for (r = 1; r < 6; r++) {
  			if (Gmap[r][c] != 0) break;
  		}
  		r--;
  		Gmap[r][c] = 1;
  	}
  	else if (t == 2) {
  		// 가로로 긴 모양
  		for (r = 1; r < 6; r++) {
  			if (Gmap[r][c+1] != 0 || Gmap[r][c] != 0) break;
  		}
  		r--;
  		Gmap[r][c] = 1, Gmap[r][c+1] = 1;
  	}
  	else { // 세로로 긴 모양
  		for (r = 1; r < 5; r++) {
  			if (Gmap[r+1][c] != 0) break;
  		}
  		r--;
  		Gmap[r+1][c] = 1, Gmap[r][c] = 1;
  	}
  }​

Earn_Point_G()

모든 행에 대해 탐색하면서 만약 그 행의 모든 열이 채워져 있으면 그 행부터 위까지 모든 행을 아래로 끌어내린다. (Fill_In_G())

int Earn_Point_G(void) {
	// 행 중에 다 1인게 있음
	for (int r = 5; r >= 2; r--) {
		int flag = 1;
		for (int c = 0; c < 4; c++) {
			if (Gmap[r][c] == 0) {
				flag = 0;
				break;
			}
		}
		if (flag == 1) {
			// 현재 r행을 삭제하고, 채워넣어야
			Fill_In_G(r);
			pnt++;
			return 1;
		}
	}
	return 0;
}

Map_Overflow_G()

0행 혹은 1행에 채워진 칸이 있는지 본다. 만약 두 행 다 채워진 칸이 있으면 2칸 내리고, 두 행 중 하나만 채워진 칸이 있으면 1칸을 내린다. 그걸 정한 후에 내리기만 하면 된다

void Map_Overflow_G(void) {
	int cnt = 0;
	// 0행 혹은 1행에 뭔가 있으면 그 만큼 뒤를 없앰
	for (int r = 1; r >= 0; r--) {
		for (int c = 0; c < 4; c++) {
			if (Gmap[r][c] == 1) {
				cnt++;
				break;
			}
		}
	}
	if (cnt == 0) return;
	for (int r = 5; r >= 2; r--) {
		for (int c = 0; c < 4; c++) {
			Gmap[r][c] = Gmap[r-cnt][c];
		}
	}
	for (int r = 0; r <= 1; r++) {
		for (int c = 0; c < 4; c++) {
			Gmap[r][c] = 0;
		}
	}
}

 

작성 코드

#include <stdio.h>
#include <string.h>
int N; // 블록을 놓은 횟수
int Gmap[6][4];
//int Gmap[4][6];
int Bmap[4][6];
int pnt; 
// t == 1: (y, x)
// t == 2: (y, x), (y, x+1)
// t == 3: (y, x), (y+1, x)

/*** BLUE MAP ***/
void Find_And_Put_B(int t, int y, int x) {
	int c;
	if (t == 1) {
		// 하나의 위치만 찾으면 됨
		for (c = 1; c < 6; c++) {
			if (Bmap[y][c] != 0) break;
		}
		c--;
		Bmap[y][c] = 1;
	}
	else if (t == 2) { // 가로로 긴 모양
		for (c = 1; c < 5; c++) {
			if (Bmap[y][c + 1] != 0) break;
		}
		c--;
		Bmap[y][c] = 1, Bmap[y][c + 1] = 1;
	}
	else { // 세로로 긴 모양
		for (c = 1; c < 6; c++) {
			if (Bmap[y][c] != 0 || Bmap[y + 1][c] != 0) break;
		}
		c--;
		Bmap[y][c] = 1, Bmap[y + 1][c] = 1;
	}
}

void Fill_In_B(int x) {
	for (int c = x; c >= 1; c--) {
		for (int r = 0; r < 4; r++) {
			Bmap[r][c] = Bmap[r][c - 1];
		}
	}
}

int Earn_Point_B(void) {
	// 열 중에 다 1인게 있음
	for (int c = 5; c >= 2; c--) {
		int flag = 1;
		for (int r = 0; r < 4; r++) {
			if (Bmap[r][c] == 0) {
				flag = 0;
				break;
			}
		}
		if (flag == 1) {
			// 현재 c열을 삭제하고, 채워넣어야
			Fill_In_B(c);
			pnt++;
			return 1;
		}
	}
	return 0;
}

void Map_Overflow_B(void) {
	int cnt = 0;
	// 0열 혹은 1열에 뭔가 있으면 그 만큼 뒤를 없앰
	for (int j = 1; j >= 0; j--) {
		for (int i = 0; i < 4; i++) {
			if (Bmap[i][j] == 1) {
				cnt++;
				break;
			}
		}
	}
	if (cnt == 0) return;
	for (int c = 5; c >= 2; c--) {
		for (int r = 0; r < 4; r++) {
			Bmap[r][c] = Bmap[r][c - cnt];
		}
	}
	for (int c = 0; c <=1; c++) {
		for (int r = 0; r < 4; r++) {
			Bmap[r][c] = 0;
		}
	}
}

void Put_On_Map_B(int t, int y, int x) { // 가로
	Find_And_Put_B(t, y, x);
	while (Earn_Point_B()); // 0이면 더이상 변동x, 아니면 다시
	Map_Overflow_B(); // 하얀지역에 있는지 확인하고 있으면 맵 변경
}

/*** GREEN MAP ***/
void Find_And_Put_G(int t, int y, int x) {
	int r =y, c = x;
	if (t == 1) {
		// 하나의 위치만 찾으면 됨
		for (r = 1; r < 6; r++) {
			if (Gmap[r][c] != 0) break;
		}
		r--;
		Gmap[r][c] = 1;
	}
	else if (t == 2) {
		// 가로로 긴 모양
		for (r = 1; r < 6; r++) {
			if (Gmap[r][c+1] != 0 || Gmap[r][c] != 0) break;
		}
		r--;
		Gmap[r][c] = 1, Gmap[r][c+1] = 1;
	}
	else { // 세로로 긴 모양
		for (r = 1; r < 5; r++) {
			if (Gmap[r+1][c] != 0) break;
		}
		r--;
		Gmap[r+1][c] = 1, Gmap[r][c] = 1;
	}
}

void Fill_In_G(int y) {
	for (int r = y; r >= 1; r--) {
		for (int c = 0; c < 4; c++) {
			Gmap[r][c] = Gmap[r-1][c];
		}
	}
}

int Earn_Point_G(void) {
	// 행 중에 다 1인게 있음
	for (int r = 5; r >= 2; r--) {
		int flag = 1;
		for (int c = 0; c < 4; c++) {
			if (Gmap[r][c] == 0) {
				flag = 0;
				break;
			}
		}
		if (flag == 1) {
			// 현재 r행을 삭제하고, 채워넣어야
			Fill_In_G(r);
			pnt++;
			return 1;
		}
	}
	return 0;
}

void Map_Overflow_G(void) {
	int cnt = 0;
	// 0행 혹은 1행에 뭔가 있으면 그 만큼 뒤를 없앰
	for (int r = 1; r >= 0; r--) {
		for (int c = 0; c < 4; c++) {
			if (Gmap[r][c] == 1) {
				cnt++;
				break;
			}
		}
	}
	if (cnt == 0) return;
	for (int r = 5; r >= 2; r--) {
		for (int c = 0; c < 4; c++) {
			Gmap[r][c] = Gmap[r-cnt][c];
		}
	}
	for (int r = 0; r <= 1; r++) {
		for (int c = 0; c < 4; c++) {
			Gmap[r][c] = 0;
		}
	}
}

void Put_On_Map_G(int t, int y, int x) {
	Find_And_Put_G(t, y, x);
	while (Earn_Point_G()); // 0이면 더이상 변동x, 아니면 다시
	Map_Overflow_G(); // 하얀지역에 있는지 확인하고 있으면 맵 변경
}

void Print_Ans(void) {
	int gcnt = 0, bcnt = 0;
	for (int i = 0; i < 6; i++) {
		for (int j = 0; j < 4; j++) {
			if (Gmap[i][j] != 0) gcnt++;
		}
	}
	for (int i = 0; i < 4; i++) {
		for (int j = 0; j < 6; j++) {
			if (Bmap[i][j] != 0) bcnt++;
		}
	}
	printf("%d\n%d", pnt, gcnt + bcnt);
}

int main(void) {
	int t, y, x;
	scanf("%d", &N);
	for (int i = 0; i < N; i++) {
		scanf("%d %d %d", &t, &y, &x);
		Put_On_Map_G(t, y, x);
		Put_On_Map_B(t, y, x);
	}
	Print_Ans();
	return 0;
}