[프로그래머스] 2019 카카오 블라인드 #7 블록 게임 (Java)

#7 블록 게임

난이도 : LEVEL4

유형 : 그래프 / 시뮬레이션

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

▸ 문제

프렌즈 블록이라는 신규 게임이 출시되었고, 어마어마한 상금이 걸린 이벤트 대회가 개최 되었다.

이 대회는 사람을 대신해서 플레이할 프로그램으로 참가해도 된다는 규정이 있어서, 게임 실력이 형편없는 프로도는 프로그램을 만들어서 참가하기로 결심하고 개발을 시작하였다.

프로도가 우승할 수 있도록 도와서 빠르고 정확한 프로그램을 작성해 보자.

게임규칙

아래 그림과 같이 1×1 크기의 블록을 이어 붙여 만든 3 종류의 블록을 회전해서 총 12가지 모양의 블록을 만들 수 있다.

 

1 x 1 크기의 정사각형으로 이루어진 N x N 크기의 보드 위에 이 블록들이 배치된 채로 게임이 시작된다. (보드 위에 놓인 블록은 회전할 수 없다). 모든 블록은 블록을 구성하는 사각형들이 정확히 보드 위의 사각형에 맞도록 놓여있으며, 선 위에 걸치거나 보드를 벗어나게 놓여있는 경우는 없다.

플레이어는 위쪽에서 1 x 1 크기의 검은 블록을 떨어뜨려 쌓을 수 있다. 검은 블록은 항상 맵의 한 칸에 꽉 차게 떨어뜨려야 하며, 줄에 걸치면 안된다.
이때, 검은 블록과 기존에 놓인 블록을 합해 속이 꽉 채워진 직사각형을 만들 수 있다면 그 블록을 없앨 수 있다.

예를 들어 검은 블록을 떨어뜨려 아래와 같이 만들 경우 주황색 블록을 없앨 수 있다.

 

빨간 블록을 가로막던 주황색 블록이 없어졌으므로 다음과 같이 빨간 블록도 없앨 수 있다.

 

그러나 다른 블록들은 검은 블록을 떨어뜨려 직사각형으로 만들 수 없기 때문에 없앨 수 없다.

따라서 위 예시에서 없앨 수 있는 블록은 최대 2개이다.

보드 위에 놓인 블록의 상태가 담긴 2차원 배열 board가 주어질 때, 검은 블록을 떨어뜨려 없앨 수 있는 블록 개수의 최댓값을 구하라.

 

▸ 제한사항

• board는 블록의 상태가 들어있는 N x N 크기 2차원 배열이다.
  • N은 4 이상 50 이하다.
• board의 각 행의 원소는 0 이상 200 이하의 자연수이다.
  • 0 은 빈 칸을 나타낸다.
  • board에 놓여있는 각 블록은 숫자를 이용해 표현한다.
  • 잘못된 블록 모양이 주어지는 경우는 없다.
  • 모양에 관계 없이 서로 다른 블록은 서로 다른 숫자로 표현된다.
  • 예를 들어 문제에 주어진 예시의 경우 다음과 같이 주어진다.

 

문제 풀이  

그래프 문제로 블록의 성질을 파악한 후 특정한 블록들의 케이스만 고려하여 시뮬레이션을 돌려주면 된다. 사실상 이런 유형은 설계와 구현의 한걸음 한걸음이 크기 때문에 선뜻 내딛기가 어려운 문제같다. 아이디어가 틀리면 수정을 왕창 해야되기 때문이다. 다행히 아이디어를 한 번에 캐치하여 빠르게 풀 수 있었다.

 

구상

주어진 블록의 생김새는 총 12개이다. 자세히 살펴보면 총 5개의 블록만 속이 꽉 채워진 블록이 될 수 있음을 알 수 있다. 왜냐하면 1x1블록은 아래의 방향으로만 수직으로 낙하하기 때문에 일명 지붕이 있는 블록들은 지붕 아래로 블록이 들어갈 수 없기 때문이다. 다음의 노란 상자로 체크한 부분을 지붕이라고 보면 된다.

5개의 블록

 

따라서 싸이클을 돌리면서 꽉 차 있는 블록이 되기 위한 조건은 지붕이 아닌 5개의 블록이면서, 해당 블록 위에 다른 블록이 없어야 한다는 점이다. 그러한 두 부분 조건을 만족하면 해당 블록을 삭제시켜주고 카운트를 해주면 된다.

 

 

설계

1. 더이상 삭제할 블록이 없을 때 까지 싸이클을 돌린다.
2.  맵을 탐색하면서 꽉 차 있는 블록이 될 조건을 만족하는 블록이 있는지 조사한다. identifyBlock(j, i, gboard[i][j])
   1. 범위를 벗어나지 않고 5개의 블록에 해당하는지 조사한다. if(isPossible(nx, ny, type))
   2. 해당 블록 위로 지붕이 있는지 조사한다. if(!isRoof(nx, nx-1, ny)
3. 2번의 조건을 만족하는 블록들을 List로 모아서 한꺼번에 삭제시켜주면서 블록당 +1 카운트를 해준다. boardUpdate(px, py, gboard[py][px]);
4. 더이상 삭제할 블록이 없으면 종료한다. if(removeList.size() ==0) break;

 

풀이 코드 

import java.util.ArrayList;
import java.util.List;

class Solution {
    static int[][] gboard;
	static boolean[][] visited;
	static int[] dx = {1, -1, 0, 0};
	static int[] dy = {0, 0, -1, 1};
	static int[] ddx = {2, -1, 1, -2 ,1};
	static int[] ddy = {0, 1, 1, 0, 0};
	static int n,m;
    public int solution(int[][] board) {
        int answer = 0;
		gboard = board;
		n = board.length; // y
		m = board[0].length; // x
		
		while(true) {
			List<int[]> removeList = new ArrayList<>();
			visited = new boolean[n][m];
			for(int i=0; i<n; i++) {
				for(int j=0; j<m; j++) {
					if(!visited[i][j] && gboard[i][j] !=0) {
						visited[i][j] = true;
						if(identifyBlock(j, i, gboard[i][j])) {
							removeList.add(new int[] {j,i});
						}
					}
				}
			}
			if(removeList.size() ==0) break;
			
			for(int[] block : removeList) {
				int px = block[0], py =block[1];
				boardUpdate(px, py, gboard[py][px]);
				answer++;
			}
			
		}
		return answer;
	}
	
	static void boardUpdate(int x, int y, int type) {
		gboard[y][x] =0;
		
		for(int i=0; i<4; i++) {
			int nx = x + dx[i];
			int ny = y + dy[i];
			if(isPossible(nx, ny, type)) {
				boardUpdate(nx, ny, type);
			}
		}
		
	}
	
	static boolean identifyBlock(int x, int y, int type) {
		int px = x, py = y+1;
		if(!isPossible(px,py,type)) return false;
		visited[py][px] = true;
		
		for(int d=0; d<5; d++) {
			int nx = px + ddx[d];
			int ny = py + ddy[d];
			if(d==4) {
				if(isPossible(nx, ny, type) && isPossible(nx-2, ny, type)) {
					if(!isRoof(nx, nx-2, ny)) {
						visited[ny][nx-2] = true;
						visited[ny][nx] = true;
						return true;
					}
				}
			}else {
				if(isPossible(nx, ny, type)) {
					if(d==0) {
                        if(!isRoof(nx, nx-1, ny)) {
							visited[ny][nx-1] = true;
							visited[ny][nx] = true;
							return true;
                        }
					}else if(d==1) {
						if(!isRoof(nx, -1, ny)) {
							visited[ny][nx+1] = true;
							visited[ny][nx] = true;
							return true;
						}
					}else if(d==2) {
						if(!isRoof(nx, -1, ny)) {
							visited[ny][nx-1] = true;
							visited[ny][nx] = true;
							return true;
						}
					}else if(d==3) {
						if(!isRoof(nx, nx+1, ny)) {
							visited[ny][nx+1] = true;
							visited[ny][nx] = true;
							return true;
						}
					}
				}
			}
		}
		return false;
		
	}
    static boolean isRoof(int x1, int x2, int y) {
		if(x2 == -1) {
			for(int i=0; i<y; i++) {
				if(gboard[i][x1] !=0) { 
					return true;
				}
			}
		}else {
			for(int i=0; i<y; i++) {
				if(gboard[i][x1] !=0 || gboard[i][x2] !=0) { 
					return true;
				}
			}
		}
		return false;
		
	}
	
	static boolean isPossible(int x, int y, int type) {
		if(x <0 || x >m-1 || y<0 || y>n-1 ||  gboard[y][x] != type) return false;
		
		return true;
	}
}