[문제풀이] 블록 게임

업데이트:

2019 Kakao Blind Recruitment 기출 문제

문제 링크 : 블록 게임

풀이 시간 : 시간 측정 불가(중간에 다른 작업 하는라)

1. 문제 풀이

먼저 블록의 종류에 따라 직사각형을 만들 수 있는지 판단해야 한다.

검은 블록은 위에서 아래로 떨어지기 때문에

ㄴ모양과 ㄴ을 뒤집은 모양, ㅗ 모양만이 직사각형을 만들 수 있다.

1) 각 블록을 저장한 뒤 각 블록의 type을 정한다.

2) 직사각형이 되는 type의 블록들만 검사한다.

3) 0에서 검은 블록이 내려와야하는 위치까지 다른 블록이 있는지 체크

4-1) 다른 블록이 없는 경우, answer를 증가하고 종료

4-2) 있지만 type이 0인 경우, 직사각형을 못 만들기 때문에 종료

4-3) 있지만 type이 0이 아닌 경우, 다른 블록을 기준으로 3번으로 이동

2. 소스 코드

    static public int solution(int[][] board) {
		answer = 0;
		// 각 block를 저장, 번호를 Key값으로 사용
		hm = new HashMap<Integer, Block>();
		for (int i = 0; i < board.length; i++) {
			for (int j = 0; j < board.length; j++) {
				if (board[i][j] != 0) {
					// 각 block의 좌표를 저장
					if (!hm.containsKey(board[i][j])) {
						hm.put(board[i][j], new Block());
					}
					hm.get(board[i][j]).y.add(i);
					hm.get(board[i][j]).x.add(j);
				}
			}
		}
		Iterator<Integer> iter = hm.keySet().iterator();
		// 각 block의 type 저장
		while (iter.hasNext()) {
			makeType(hm.get(iter.next()));
		}
		iter = hm.keySet().iterator();
		// 각 block이 직사각형이되는지 체크
		while (iter.hasNext()) {
			Block b = hm.get(iter.next());
			// type이 0이 아니고 이미 check가 되었느지 
			if (b.type != 0 && !b.check) {
				search(b, board);
			}
		}
		return answer;
	}
	static boolean check(int[][] board, int y, int x) {
		for (int i = 0; i <= y; i++) {
			// 만약 검은 색 돌이 떨어지는 곳에 다른 블록이 있을 때
			if (board[i][x] != 0) {
				if (hm.get(board[i][x]).type == 0) {
					// type이 0이면 직사각형을 못 만들기 때문에 
					return false;
				} else {
					// 위에 있는 block이 직사각형이 되는지 판단
					if (!search(hm.get(board[i][x]), board)) {
						return false;
					}
				}
			}
		}
		return true;
	}
	static boolean search(Block b, int[][] board) {
		int y = b.y.get(0);
		int x = b.x.get(0);
		// 타입별로 가능한지 체크
		if (b.type == 1) {
			if(!check(board, y, x+1)) {
				return false; 
			}
			if(!check(board, y, x+2)) {
				return false; 
			}
		} else if (b.type == 2) {
			if(!check(board, y+1, x-1)) {
				return false; 
			}
		} else if (b.type == 3) {
			if(!check(board, y+1, x+1)) {
				return false; 
			}
		} else if (b.type == 4) {
			if(!check(board, y, x-2)) {
				return false; 
			}
			if(!check(board, y, x-1)) {
				return false; 
			}
		} else {
			if(!check(board, y, x+1)) {
				return false; 
			}
			if(!check(board, y, x-1)) {
				return false; 
			}
		}
		answer++;
		b.check = true;
		// 만들 수 있으면 block 삭제
		for (int i = 0; i < 4; i++) {
			board[b.y.get(i)][b.x.get(i)] = 0;
		}
		return true;
	}

	static void makeType(Block b) {
		// 직사각형을 못만드는 경우
		if (b.y.get(0) == b.y.get(1)) {
			b.type = 0;
		} else {
			if (b.y.get(1) == b.y.get(2) && b.y.get(2) == b.y.get(3)) {
				if (b.x.get(0) == b.x.get(1)) {
					// 가로로 긴 ㄴ 모양
					b.type = 1;
				} else if (b.x.get(0) == b.x.get(1) + 1) {
					// ㅗ 모양
					b.type = 5;
				} else {
					// 가로로 긴 ㄴ 모양 반대
					b.type = 4;
				}
			} else if (b.y.get(2) == b.y.get(3)) {
				if (b.x.get(0) == b.x.get(2)) {
					// 세로로 긴 ㄴ 모양
					b.type = 3;
				} else {
					// 세로로 긴 ㄴ 모양 반대
					b.type = 2;
				}
			}
		}
	}

	static class Block {
		int type;
		boolean check;
		ArrayList<Integer> y;
		ArrayList<Integer> x;

		Block() {
			this.type = 0;
			this.check = false;
			this.y = new ArrayList<Integer>();
			this.x = new ArrayList<Integer>();
		}
	}

3. 후기

다 풀고 해설을 봤을 때는 약간 풀이 방법이 다르지만

직사각형을 만들 수 있는 경우를 찾는 것은 똑같다.

참고