[백준 20061번 모노미노도미노2] - C++

[백준 20061번 모노미노도미노2]
https://www.acmicpc.net/problem/20061

문제 이름이 읽기 어렵다. 문제에서 요구하는 기능이 몇 가지 있었고, 빠짐없이 꼼꼼히 구현하는 것이 포인트였다. 따로 알고리즘을 요구하지 않는 단순 구현 문제였다.

풀이

문제에서 크게 세 가지의 기능을 요구한다.
1. 블럭을 빨간색 영역에서 초록색, 파란색 영역으로 각각 옮기기
2. 행/열이 꽉 찼을 때, 꽉찬 행/열을 삭제하고 아래로 혹은 오른쪽으로 당겨서 채우기
3. 연한 칸에 블럭이 있을 때 맨 아래 혹은 맨 오른쪽부터 삭제하고 당겨 채우기

별다른 알고리즘이 없기 때문에 하나씩 기능을 구현해야 한다. 필자는
moveBlock(), removeAnyFilledRowOrCol(), blocksInSpecialArea()
이렇게 세 개의 메서드로 요구 사항을 모두 구현하였다.

모두 구현해도 제출하자마자 틀렸습니다라고 나올 경우 아래의 2가지를 살펴봐야 한다.

1.

moveBlock() 부분에서 C++로 코딩을 할 때 while 문으로 블럭을 옮기게 되는데 조건에서 순서가 중요하다. while(i<9 && !bd[i+1][y])와 같이 index의 범위를 먼저 제한하는 조건이 앞에 오고, 그 뒤에 보드 위에 다른 블럭의 존재를 검사해야 한다. 반대로 조건문을 작성하면 C++ 특성상 자바처럼 Index 에러가 나지 않고 어떤 알 수 없는 값이 튀어 나올 수 있어 주의가 필요하다.

2.

removeAnyFilledRowOrCol() 부분에서 행/열이 다 채워져 삭제한 이후에 블럭을 당겨올 때, 연한 칸에 존재하는 블럭도 같이 당겨와야 한다. 주어진 테스트 케이스에는 이 경우에 해당하는 경우가 없기 때문에 주어진 테케로는 확인할 수 없는 부분이었다. 필자도 이 부분 때문에 제출하자마자 틀렸습니다가 나왔고, 이후에 수정하고 정답 처리를 받았다.

C++ 코드

#include <iostream>
#include <cstring>
#include <algorithm>
#include <cmath>
#include <queue>
#include <vector>
#include <utility>  // pair
#include <tuple>
#include <stack>
// #include <map>
#include <unordered_map>
#define ll long long
#define INF 1e9
using namespace std;

int ans = 0;
int n;
int bd[10][10];
int blocks = 0;
int t,x,y;

void moveBlock() {
	int i,j;
	if(t==1) {  // 1x1
		// green
		i = x;
		while(i<9 && !bd[i+1][y]) {
			i++;
		}
		// blue
		j = y;
		while(j<9 && !bd[x][j+1]) {
			j++;
		}
	} else if(t==2) {  // 1x2
		// green
		i = x;
		while(i<9 && !bd[i+1][y] && !bd[i+1][y+1]) {
			i++;
		}
		// blue
		j = y+1;
		while(j<9 && !bd[x][j+1]) {
			j++;
		}
	} else if(t==3) {
		// green
		i = x+1;
		while(i<9 && !bd[i+1][y]) {
			i++;
		}
		// blue
		j = y;
		while(j<9 && !bd[x][j+1] && !bd[x+1][j+1]) {
			j++;
		}
	}

	if(t==1) {
		bd[i][y] = 1;
		bd[x][j] = 1;
	} else if(t==2) {
		bd[i][y] = 1; bd[i][y+1] = 1;
		bd[x][j] = 1; bd[x][j-1] = 1;
	} else if(t==3) {
		bd[i-1][y] = 1; bd[i][y] = 1;
		bd[x][j] = 1; bd[x+1][j] = 1;
	}
	
	return;	
}

void removeAnyFilledRowOrCol() {
	// green rows
	int start = -1;
	int removed = 0;
	for(int i=6;i<10;++i) {
		for(int j=0;j<4;++j) {
			if(!bd[i][j]) break;  // not a filled row

			if(j==3) {
				start = max(start, i);
				removed++;
			}
		}
	}

	if(start > -1) {
		for(int i=start-removed;i>=4;--i) {
			for(int j=0;j<4;++j) {
				bd[i+removed][j] = bd[i][j];
				bd[i][j] = 0;
			}
		}


		ans += removed;
	}

	// blue cols
	start = -1;
	removed = 0;
	for(int j=6;j<10;++j) {
		for(int i=0;i<4;++i) {
			if(!bd[i][j]) break; // not a filled col

			if(i==3) {
				start = max(start,j);
				removed++;
			}
		}
	}

	if(start > -1) {
		for(int j=start-removed;j>=4;--j) {
			for(int i=0;i<4;++i) {
				bd[i][j+removed] = bd[i][j];
				bd[i][j] = 0;
			}
		}

		ans += removed;
	}

	return;
}

void blocksInSpecialArea() {
	// green
	int rows = 0;
	for(int i=4;i<=5;++i) {
		for(int j=0;j<4;++j) {
			if(bd[i][j]) {
				rows++;
				break;
			}
		}
	}

	if(rows > 0) {
		for(int i=9-rows;i>=4;--i) {
			for(int j=0;j<4;++j) {
				bd[i+rows][j] = bd[i][j];
			}
		}
		for(int i=4;i<=5;++i) {
			for(int j=0;j<4;++j) {
				bd[i][j] = 0;
			}
		}
	}

	// blue
	int cols = 0;
	for(int j=4;j<=5;++j) {
		for(int i=0;i<4;++i) {
			if(bd[i][j]) {
				cols++;
				break;
			}
		}
	}

	if(cols > 0) {
		for(int j=9-cols;j>=4;--j) {
			for(int i=0;i<4;++i) {
				bd[i][j+cols] = bd[i][j];
			}
		}
		for(int j=4;j<=5;++j) {
			for(int i=0;i<4;++i) {
				bd[i][j] = 0;
			}
		}
	}
}

void sol() {
	moveBlock();
	removeAnyFilledRowOrCol();
	blocksInSpecialArea();
}

int main(void) {
	// ios_base :: sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
	scanf("%d", &n);
	for(int i=0;i<n;++i) {
		scanf("%d%d%d", &t,&x,&y);

		sol();
	}

	for(int i=0;i<4;++i) {
		for(int j=6;j<10;++j) {
			if(bd[i][j]) {
				blocks++;
			}
		}
	}

	for(int i=6;i<10;++i) {
		for(int j=0;j<4;++j) {
			if(bd[i][j]) {
				blocks++;
			}
		}
	}
	

	printf("%d\n", ans);
	printf("%d\n", blocks);
	
	return 0;
}

채점 결과