[프로그래머스] 블록 게임 (자바)

 

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

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

 

약 6%의 정답률인 문제입니다.

필요한 기능들을 구현하면 쉽게 풀 수 있는 문제였습니다.

 

2020/08/29 - [문제풀이/자바] - [프로그래머스] 매칭 점수 (자바)

[프로그래머스] 매칭 점수 (자바)

프로그래머스는 위의 문제를 레벨 3으로 측정하고 이 문제는 레벨 4로 측정했습니다.

 

검은 블록을 위에서부터 떨어트립니다. 주어지는 블록에서 1번의 맨 마지막 모양과 2번의 2번째 블록의 모양을 보면 검은 블록이 2개가 떨어지면 사라집니다. 검은 블록을 2줄 떨어트리면 조건이 맞다면 모든 블록을 없앨 수 있습니다.

 

그래서 가장 위에 검은 블록 2줄을 채우고 완전 탐색으로 조건에 맞는 블록을 1개씩 지웠습니다.

---

전역 변수

map[][] = 주어진 배열에서 검은 블록을 쌓는 등 조작을 할 배열

board [][] = 문제에서 주어지는 배열

n = board의 크기

answer = 사라지는 블록의 개수

finish = 검은 블록을 쌓아도 사라지는 블록이 없으면 true

메소드

int solution

board를 map에 복사해줍니다. 이제부터 map을 조작하여 사라질 블록을 찾습니다.

(black 호출)

 

void black

map의 가장 위에 검은 블록을 2개 쌓아줍니다.

지붕에 눈 덮이듯 가장 위의 블록에만 쌓아줍니다.

블록을 쌓았다면 완전 탐색을 진행합니다.

(search 호출)

 

void search

현재 좌표로 시작하여 3x2, 2x3의 직사각형을 검사합니다.

(remove 호출)

 

void remove

파라미터로 받은 좌표에 대해 검사합니다.

2x3, 3x2 순으로 검사하는데, 각 직사각형은 검은 블록 2개와 동일한 블록 4개로 구성되어야 합니다.

black과 other는 각 블록의 개수를 세고 block은 블록의 종류를 저장합니다.

 

조건을 만족하면 answer를 1 증가시키고, finish를 false로 바꿔서 한 번 더 반복하도록 합니다.

해당하는 블록은 board에서 0으로 바꿔 없애줍니다.

(check 호출)

 

boolean check

좌표 값이 적절한지 검사합니다.

 

public class pm블록게임 {

	public int map[][];
	public int n;
	public int board[][];
	public int answer;
	public boolean finish;

	public int solution(int[][] board) {
		n = board.length;
		answer = 0;
		map = new int[n][n];
		this.board = board;
		finish = false;

		while(!finish) {
			finish = true;
			for(int i = 0; i < n; i++)
				map[i] = board[i].clone();
			black();
		}

		return answer;
	}

	public void black() {
		for(int i = 0; i < n; i++) {
			int count = 2;
			int j = 0;
			for(; j < n; j++) 
				if(map[j][i] != 0)
					break;
			j -= 1;
			while(count > 0 && j >= 0){
				map[j--][i] = -1;
				count--;
			}
		}

		search();
	}

	public void search() {
		for(int i = 0; i < n; i++) {
			for(int j = 0; j < n; j++) {
				remove(i, j);
			}
		}
	}

	public void remove(int x, int y) {
		int black = 2;
		int other = 4;
		int block = -2;

		l:	for(int i = 0; i < 2; i++) {
			for(int j = 0; j < 3; j++) {
				int nx = x + i;
				int ny = y + j;

				if(check(nx, ny)) {
					if(map[nx][ny] == -1)
						black--;
					else if(map[nx][ny] == 0)
						break l;
					else {
						if(block == -2)
							block = map[nx][ny];
						if(block != map[nx][ny])
							break l;
						other--;
					}
				}
			}
		}

		if(black == 0 && other == 0) {
			answer++;
			finish = false;
			for(int i = 0; i < 2; i++) {
				for(int j = 0; j < 3; j++) {
					int nx = x + i;
					int ny = y + j;

					board[nx][ny] = 0;
				}
			}
			return;
		}

		black = 2;
		other = 4;
		block = -2;

		l:	for(int i = 0; i < 3; i++) {
			for(int j = 0; j < 2; j++) {
				int nx = x + i;
				int ny = y + j;

				if(check(nx, ny)) {
					if(map[nx][ny] == -1)
						black--;
					else if(map[nx][ny] == 0)
						break l;
					else {
						if(block == -2)
							block = map[nx][ny];
						if(block != map[nx][ny])
							break l;
						other--;
					}
				}
			}
		}

		if(black == 0 && other == 0) {
			answer++;
			finish = false;
			for(int i = 0; i < 3; i++) {
				for(int j = 0; j < 2; j++) {
					int nx = x + i;
					int ny = y + j;

					board[nx][ny] = 0;
				}
			}
			return;
		}

	}

	public boolean check(int x, int y) {
		return x >= 0 && y >= 0 && x < n && y < n;
	}
}