2019 카카오 코딩 테스트 블록게임 java

문제 설명

 

블록게임

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

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

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

게임규칙

아래 그림과 같이 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에 놓여있는 각 블록은 숫자를 이용해 표현한다.
  • 잘못된 블록 모양이 주어지는 경우는 없다.
  • 모양에 관계 없이 서로 다른 블록은 서로 다른 숫자로 표현된다.
  • 예를 들어 문제에 주어진 예시의 경우 다음과 같이 주어진다.

 

 

 

나의 풀이

 

문제 풀이의 핵심은, 2*3박스 or 3*2박스 안에서 없앨 수 있는 모형(4개의 블럭으로 이루어진 모양을 모형이라 칭하기로)이 있느냐를 체크하는 것이었다. 순서를 나열해보면

 

 1. 매번 2*3, 3*2 박스에서 좌상단 블럭을 기준으로 해당 박스 안에서 없앨 수 있는 모형이 있는지 체크한다.

 2. 모형을 하나 제거할 경우 다른 모형이 제거가 가능해졌을 수 도 있으므로, 전체 보드를 다시 스캔한다.

 

이 두 가지가 핵심 방법이다.

 

 1번 제거할 수 있는 모형인지 체크는 find() 메서드로 블럭의 크기를 지정해 준 후에 h*w = 6칸의 박스에서 4개는 같은 수가 있고 나머지 2개는 0의 값인지(=공백인지) 체크한다. 그리고 0의 블럭(=공백)은 체울 수 있는지 canFill() 메서드로 체크한다.

 

공백 블럭을 체울 수 있는지는 보드에서 해당 블럭의 상단이 모두 공백일 경우만 가능하다 보고, 공백 블럭의 위치를 파라미터로 canFill() 메서드로 상단이 비어있는지만 확인해준다.

 

 2번 모형을 하나 제거할 경우 다른 모형이 제거가 가능해졌을 수 도 있으니 다시 전체 스캔은 do while문으로 반복한다. 만약 전체 보드를 끝까지 스캔했는데 제거된 모형이 없는 경우, 전체 보드에서 추가적으로 제거할 수 있게된 모형도 없으므로 종료한다.

 

//코드에 주석으로 풀이를 추가했다.

 

 

전체 코드

class Solution {
    int N;
    int[][] Board;
    
    //채울수 있는지 확인. 해당 블럭 위가 모두 비어있으면 가능하다.
    boolean canFill(int row, int col) {
        for(int i=0; i<row; i++) {
            if(Board[i][col] != 0) return false;
        }
        return true;
    }
    
    //현재 블럭을 기준으로 h*w 만큼 박스 안에서 모형을 지울 수 있는지 검사
    boolean find(int row, int col, int h, int w) {
        int emptyCnt = 0;
        int lastVal = -1;
        for(int r = row; r < row+h; r++) {
            for(int c = col; c<col+w; c++) {
                if(Board[r][c] == 0) {
                    //(r,c) 블럭이 0이면서 지울 수 있는지 체크, 지울 수 없다면 리턴 false
                    if(!canFill(r,c)) return false;
                    //현재 w*h 크기 박스에서 빈공간이 2개를 초과한다면 리턴 false;
                    if(++emptyCnt > 2) return false;
                } else {
                    //(r,c) 블럭이 0이 아닌 경우,
                    // w*h 블럭 안에서 다른 숫자가 2개 이상 나온 경우 리턴 false;
                    if((lastVal!= -1) && (lastVal!=Board[r][c]))
                        return false;
                    lastVal = Board[r][c];
                }
            }
        }
        
        //박스가 모두 체워지면 모형이 없어지기 때문에 0으로 값을 변경한다.
        for(int r = row; r < row+h; r++) {
            for(int c = col; c < col+w; c++) {
                Board[r][c] = 0;
            }
        }
        
        return true;
    }
    
    public int solution(int[][] board) {
        Board = board;
        N = board.length;
        int cnt;
        int answer = 0;
        
        //하나의 모형이 삭제되었을때, 삭제가 불가능하던 모형이 삭제가 가능해질 수 있다.
        //따라서 모형이 하나라도 삭제될 경우 보드 전체 범위를 다시 스캔한다.
        do{
            cnt = 0;
            for(int i=0; i<N; i++) {
                for(int j = 0; j<N; j++) {
                    //세로(row수)2, 가로(col수)3 의 박스를 검사
                    if(i<=N-2 && j<=N-3 && find(i,j, 2, 3)) {
                        cnt++;
                        
                    } 
                    //세로(row수)3, 가로(col수)2 의 박스를 검사
                    else if(i<=N-3 && j<=N-2 && find(i,j,3,2)) {
                        cnt++;
                    }
                }
            }
            answer += cnt;
        } while(cnt != 0);
        
        return answer;
    }
}