[백준 20061번] 모노미노도미노 2 (java)

20061번: 모노미노도미노 2

초록색 블럭과 파란색 블럭을 각각 boolean형의 2차원 배열로 생성한다.

(i, j)칸에 블럭이 있으면 true, 블럭이 없으면 false가 들어간다.

boolean[][] blue = new boolean[4][6];
boolean[][] green = new boolean[6][4];

 

이 문제에서 크게 3가지 동작으로 나누었다.

 

1. 새로운 블럭 쌓기 : stack(int t, int x, int y)

 

2. 한 행(혹은 열)에 블럭이 다 차면, 점수를 증가시키고 해당 행(혹은 열) 비우기 : remove()

 

3. 연한 부분에 블럭이 있으면, 그 행(혹은 열) 개수만큼 블럭 이동하기 : move()

 

 

1. 새로운 블럭 쌓기

t가 1일 때, 2일 때, 3일 때를 조건문으로 나누어서 풀어야 한다.

 

① t = 1

초록 영역에서 5번째 행부터 0번째 행(i)까지 거꾸로 탐색하면서 green[i][y] = false인 칸을 찾는다.

그런데, 여기서 주의해야할 점이 있다.

false칸을 찾았다고 끝이 아니라, 같은 열에 있으면서 해당 칸보다 위쪽의 있는 칸들에 모두 블럭이 없어야 한다.

 

예를 들어, 초록색 영역이 현재 아래 그림과 같고, 1x1 짜리 블럭을 빨간 영역의 (2,2)에 두었다고 하자.

초록색 영역의 5번째 행부터 0번째 행까지 차례대로 green[i][2] = false인 부분을 찾으면

i = 4일 때, 즉 4번째 행에서 멈추게 된다. 

그러면 green[4][2] = false이니, green[4][2]에 블럭을 두면 되는 것이 아니라, 4번째 행보다 위에 있는

행들 중에서 green[k][2] = true(0<=k && k<i)이 있는지를 확인해야 한다. 만약 true가 있으면 새로운 블럭이 내려오는 과정에서 기존의 블럭에 가로막혀 4번째 행에 내려갈 수가 없기 때문이다.

 

아래 그림에서는 블럭이 내려오다가 2번째 행의 (2, 2)의 블럭에 막혀 4번째 행까지 내려오지 못하게 된다.

따라서, 매번 위의 행들을 체크해줘야 한다.

 

if (t == 1) {
    // green 영역에서 블럭을 배치할 위치 찾기
	for (int i = 5; i >= 0; i--) {
		if (!green[i][y]) {  // green[i][y] = false이면

			// i번째 행보다 위의 행들 중 동일 열에 true가 있는지 확인
			boolean flag = true;
			for (int r = 0; r < i; r++) {
				if (green[r][y]) {
					flag = false;
					break;
				}
			}

			if (flag) {
				green[i][y] = true;
				break;
			}
		}
	}

    // blue 영역에서 블럭을 배치할 위치 찾기
	for (int i = 5; i >= 0; i--) {
		if (!blue[x][i]) {

			boolean flag = true;
			for (int c = 0; c < i; c++) {
				if (blue[x][c]) {
					flag = false;
					break;
				}
			}
			if (flag) {
				blue[x][i] = true;
				break;
			}
		}
	}
}

 

② t = 2

t = 2는 1x2 블럭을 쌓는 경우이다.

t = 1일 때와 마찬가지로 5번째 행부터 0번째 행부터 거꾸로 탐색하면서 블럭을 배치할 위치를 찾는다.

t = 1일 때는 블럭이 한 칸짜리였지만, 이번에는 두 칸짜리이므로 블럭이 들어가게 될 두 칸 모두 false인지를 검사해야 한다. 

if (t == 2) { // 1x2 블럭
		// green 영역에 블럭 배치
		for (int i = 5; i >= 0; i--) {
			if (!green[i][y] && !green[i][y + 1]) {
				boolean flag = true;
				for (int r = 0; r < i; r++) {
					if (green[r][y] || green[r][y + 1]) {
						flag = false;
						break;
					}
			     }
			     if (flag) {
					green[i][y] = true;
					green[i][y + 1] = true;
					break;
				}
			}
		}

		// blue 영역에 블럭 배치
		for (int i = 5; i >= 1; i--) {
			if (!blue[x][i] && !blue[x][i - 1]) {

				boolean flag = true;
				for (int c = 0; c < i - 1; c++) {
					if (blue[x][c]) {
						flag = false;
						break;
					}
				}
				if (flag) {
					blue[x][i] = true;
					blue[x][i - 1] = true;
					break;
				}
			}
		}
	}

 

③ t = 3

if (t == 3) { // 2x1 타일
		// green 영역에 블럭 배치
		for (int i = 5; i >= 1; i--) {
			if (!green[i][y] && !green[i - 1][y]) {

				boolean flag = true;
				for (int r = 0; r < i - 1; r++) {
					if (green[r][y]) {
						flag = false;
						break;
					}
				}

				if (flag) {
					green[i][y] = true;
					green[i - 1][y] = true;
					break;
				}
			}
		}

		// blue 영역에 블럭 배치
		for (int i = 5; i >= 0; i--) {
			if (!blue[x][i] && !blue[x + 1][i]) {
				boolean flag = true;
				for (int c = 0; c < i; c++) {
					if (blue[x][c] || blue[x + 1][c]) {
						flag = false;
						break;
					}
				}

				if (flag) {
					blue[x][i] = true;
					blue[x + 1][i] = true;
					break;
				}
			}
		}
	}

 

 

 

2. 한 행(혹은 열)에 블럭이 다 차면, 점수를 증가시키고 해당 행(혹은 열) 비우기

초록색 영역의 각 행에 모든 블럭이 차 있는지 검사한다.

만약 블럭으로 꽉 차있는 행을 발견하면, 그 행의 칸을 모두 false로 바꾸고(블럭 비우기),

 

해당 행보다 위쪽의 행의 값으로 덮어쓰기 한다. 그러면 그 위쪽의 행은 바로 그 위의 행의 값으로 덮어쓰기 한다. 이런식으로 1번째 행까지 덮어쓰기를 반복한다. 이는 블럭을 비우고 나서 그 위에 있던 블럭들을 한칸씩 아래로 내려오도록 하는 동작이다.

덮어쓰기를 완료하면, 0번째 행은 첫 행이므로 그 위의 행이 없어서 덮어쓸게 없다.

따라서, 0번째 행의 값들을 모두 false로 만들어주는 과정을 반드시 해야한다.

 

파란색 영역도 동일하게 처리한다.

	public static void remove() {

		// green 영역 블럭 제거
		for (int i = 0; i < 6; i++) {

			boolean flag = true;
			for (int j = 0; j < 4; j++) {
				if (!green[i][j]) {
					flag = false;
					break;
				}
			}

			if (flag) {
				score++;

				for (int k = i - 1; k >= 0; k--) {
					for (int j = 0; j < 4; j++) {
						green[k + 1][j] = green[k][j];
					}
				}
				// 0번째 행 비우기
				for (int j = 0; j < 4; j++) {
					green[0][j] = false;
				}
			}
		}

		// blue 영역 블럭 제거
		for (int i = 0; i < 6; i++) {

			boolean flag = true;
			for (int j = 0; j < 4; j++) {
				if (!blue[j][i]) {
					flag = false;
					break;
				}
			}

			if (flag) {
				score++;

				for (int k = i - 1; k >= 0; k--) {
					for (int j = 0; j < 4; j++) {
						blue[j][k + 1] = blue[j][k];
					}
				}
				// 0번째 열 비우기
				for (int j = 0; j < 4; j++) {
					blue[j][0] = false;
				}
			}
		}

	}

 

3. 연한 부분에 블럭이 있으면, 그 행(혹은 열) 개수만큼 블럭 이동하기

우선, 연한 부분의 각 행(혹은 열)에 블럭이 있는지를 확인하고, 블럭이 있으면 cnt를 증가시킨다.

 

만약 0번째 행(혹은 열) 1번째 행(혹은 열) 모두에 블럭이 하나라도 있으면 cnt는 2가 된다.

둘 중 하나에만 블럭이 존재하면 cnt는 1이 된다.

연한 부분에 블럭이 존재하지 않으면 cnt는 0이 된다. 

 

그리고 cnt가 0보다 크면, cnt만큼 블럭을 밀어주는 동작을 수행한다.

이 동작은 아까 2번에서 설명한 방식대로 현재 행을 바로 위의 행으로 덮어쓰는 식으로 진행할 수 있다.

public static void move() {

	// green 영역 연한 부분 블록 있으면 이동
	int cnt = 0;
	for (int i = 0; i < 2; i++) {
		for (int j = 0; j < 4; j++) {
			if (green[i][j]) {
				cnt++;
				break;
			}
		}
	}

	if (cnt > 0) {
		for (int i = 5 - cnt; i >= 0; i--) {
			for (int j = 0; j < 4; j++) {
				green[i + cnt][j] = green[i][j];
			}
		}
		for (int i = 0; i < cnt; i++) {
			for (int j = 0; j < 4; j++) {
				green[i][j] = false;
			}
		}
	}

	// blue 영역 연한 부분 블록 있으면 이동
	cnt = 0;
	for (int i = 0; i < 2; i++) {
		for (int j = 0; j < 4; j++) {
			if (blue[j][i]) {
				cnt++;
				break;
			}
		}
	}

	if (cnt > 0) {
		for (int i = 5 - cnt; i >= 0; i--) {
			for (int j = 0; j < 4; j++) {
				blue[j][i + cnt] = blue[j][i];
			}
		}
		for (int i = 0; i < cnt; i++) {
			for (int j = 0; j < 4; j++) {
				blue[j][i] = false;
			}
		}
	}

}

 

 

이렇게 N번 반복할 때마다 1번, 2번, 3번 동작을 차례대로 수행하여 문제를 해결할 수 있다.

N번을 반복 후에 score 변수에 있는 값이 최종 점수가 된다. 

 

 

전체 코드 :