2019 - 블록 게임

https://programmers.co.kr/learn/courses/30/lessons/42894#

코딩테스트 연습 - 블록 게임

[ 문제풀이 ]

2019 카카오 블라인드 기출 마지막 문제로 전형적인 완전 탐색 문제이다. 모든 블록을 하나씩 비교해가면서 제거할 수 있다면 제거해주면 된다.

​사실 모든 블록을 확인할 필요가 없다. 3x2 or 2x3 형태의 직사각형이 되기 위해선 검은 블록이 2개가 필요한데 검은 블록은 위에서 떨어지기 때문에 빈 공간 2개가 이미 존재한 블록에 가려진 블록들은 제거 대상이 될 수가 없다.

따라서 2x3 형태의 블록 3개, 3x2 형태의 블록 2개, 총 5개의 블록에 대해서만 확인해주면 된다.

​먼저 검은 블록(-1)들이 가능한 모든 칸에 채워준 후 5개의 블록을 비교해가면서 제거해주면 된다. 주의해야 할 점은 제거해야 할 블록은 검은 블록 2개, 같은 블록 4개로 이루어져야 한다.

class Solution {
	int answer, N;
	boolean finish;
	
	//block1 : 2x3 가능한 블록
	int[][][] block1 = {{{1,0,0},{1,1,1}}, {{0,0,1},{1,1,1}}, {{0,1,0},{1,1,1}}};
	//block2 : 3x2 가능한 블록
	int[][][] block2 = {{{0,1},{0,1},{1,1}}, {{1,0},{1,0},{1,1}}};

	public int solution(int[][] board) {
		N = board.length;
		do {
			finish = false;
			
			createBlackBlock(board);
			simulateWith2x3(board);
			simulateWith3x2(board);
		} while (finish);

		return answer;
	}

	//검은 블록을 채울 수 있는 모든 곳에 채워줌
	public void createBlackBlock(int[][] board) {
		for (int j = 0; j < N; ++j) {
			for (int i = 0; i < N; ++i) {
				if (board[i][j] > 0) break;
				board[i][j] = -1;
			}
		}
	}

	public void simulateWith2x3(int[][] board) {
		for (int k = 0; k < 3; ++k) {
			for (int i = 0; i < N - 1; ++i) {
				for (int j = 0; j < N - 2; ++j) {
					int cnt = 0, flag = 0;
					//flag : 빈공간, 검은 블록을 제외한 블록을 저장
					boolean mark = true;

					for (int y = 0; y < 2; ++y) {
						if (!mark) break;
						for (int x = 0; x < 3; ++x) {
							//k번째 block1의 1인 경우
							if (block1[k][y][x] == 1) {
								//현재 board가 빈공간이거나 검은 블록인 경우
								if (board[i + y][j + x] <= 0) {
									mark = false;
									break;
								}
								
								if (flag == 0) {
									flag = board[i + y][j + x];
									cnt++;
								} else {
									//이전에 저장한 flag와 현재 board가 다르면
									if (flag != board[i + y][j + x]) {
										mark = false;
										break;
									}
									cnt++;
								}
							} 
							//k번째 block1의 0인 경우
							else {
								//검은 블록을 제외한 블록이 존재하면
								if (board[i + y][j + x] >= 0) {
									mark = false;
									break;
								}
							}
						}
					}

					//제거할 수 있음
					if (cnt == 4) {
						answer++;
						finish = true;
						
						//블록 6개를 제거
						for (int y = 0; y < 2; ++y) {
							for (int x = 0; x < 3; ++x) {
								board[i + y][j + x] = 0;
							}
						}
					}
				}
			}
		}
	}
	
	public void simulateWith3x2(int[][] board) {
		for (int k = 0; k < 2; ++k) {
			for (int i = 0; i < N - 2; ++i) {
				for (int j = 0; j < N - 1; ++j) {
					int cnt = 0, flag = 0;
					//flag : 빈공간, 검은 블록을 제외한 블록을 저장
					boolean mark = true;

					for (int y = 0; y < 3; ++y) {
						if (!mark) break;
						for (int x = 0; x < 2; ++x) {
							//k번째 block2의 1인 경우
							if (block2[k][y][x] == 1) {
								//현재 board가 빈공간이거나 검은 블록인 경우
								if (board[i + y][j + x] <= 0) {
									mark = false;
									break;
								}
								
								if (flag == 0) {
									flag = board[i + y][j + x];
									cnt++;
								} else {
									//이전에 저장한 flag와 현재 board가 다르면
									if (flag != board[i + y][j + x]) {
										mark = false;
										break;
									}
									cnt++;
								}
							} 
							//k번째 block2의 0인 경우
							else {
								//검은 블록을 제외한 블록이 존재하면
								if (board[i + y][j + x] >= 0) {
									mark = false;
									break;
								}
							}
						}
					}

					//제거할 수 있음
					if (cnt == 4) {
						answer++;
						finish = true;
						
						//블록 6개를 제거
						for (int y = 0; y < 3; ++y) {
							for (int x = 0; x < 2; ++x) {
								board[i + y][j + x] = 0;
							}
						}
					}
				}
			}
		}
	}
}