2019 KAKAO BLIND - 블록 게임

1. 문제

2019 KAKAO BLIND 블록 게임

2. 접근

기본적으로 배열을 완전 탐색하는 문제라고 생각했다.

2.1 첫 번째 시도

처음에는 모든 세로줄을 한개씩 검사해서 한 개의 행씩 1x1 블록을 놓은 뒤, 블록이 지워지는지 확인해보려고 했다. 1x1 블록을 -1로 두고 나머지 블록과 검사를 진행했는데 이게 자꾸 예외도 많이 나고 1x1블록끼리 사라지고 난리가 나서 포기했다.. 물론 이 방법으로도 문제가 풀린다. 내 구현력이 떨어지는 듯...

2.2 두 번째 시도

어차피 1x1 블록은 위에서 떨어지므로 애초에 지워질 수 있는 블록의 모양은 정해져 있다.
위에서 블록을 떨어뜨렸을 때 직사각형을 만들 수 있는 블록만 삭제할 수 있다. 그런 블록은
빨강 3번, 빨강 4번, 주황 2번, 주황 3번, 파랑1번 이다
그래서 위에 해당하는 5개의 블록들에 대해 1x1 블록이 들어갈 자리의 위쪽 인덱스를 모두 탐색해서 아무 블록도 없으면 1x1 블록을 떨어뜨릴 수 있으므로 삭제할 수 있다. 5개 블록에 대한 경우의 수를 모두 탐색했는데 지워지는 블록이 없다면 더 이상 지울 블록이 없는 것이므로 결과를 리턴한다.

3. 코드

class Solution {
    public static int answer = 0;
    public int solution(int[][] board) {

        // 삭제할 블록이 없을 때 까지 반복
        while(isDeleteRedThree(board) || isDeleteRedFour(board) ||
                isDeleteOrangeTwo(board)|| isDeleteOrangeThree(board) || isBlueOne(board));
        return answer;
    }

    public boolean isDeleteRedThree(int[][] board){ // 빨강 3번

        int temp = answer;
        for(int i=0;i<=board.length-2;i++){
            for(int j=0;j<=board.length-3;j++){
                if(board[i][j]!=0 && checkTop(board,i,j+1,i,j+2)){
                    if(board[i][j]==board[i+1][j] && board[i+1][j] == board[i+1][j+1] &&
                            board[i+1][j+1] == board[i+1][j+2]){
                        board[i][j] = 0;
                        board[i+1][j] = 0;
                        board[i+1][j+1] = 0;
                        board[i+1][j+2] = 0;
                        answer++;
                    }
                }
            }
        }

        if(temp==answer){
            return false; // 더 이상 지울게 없다
        } else {
            return true;
        }

    }

    public boolean isDeleteRedFour(int[][] board){ // 빨강 4번

        int temp = answer;
        for(int i=0;i<=board.length-3;i++){
            for(int j=1;j<=board.length-1;j++){
                if(board[i][j]!=0 && checkTop(board,i,j-1,i+1,j-1)){
                    if(board[i][j]==board[i+1][j] && board[i+1][j] == board[i+2][j] &&
                            board[i+2][j] == board[i+2][j-1]){
                        board[i][j] = 0;
                        board[i+1][j] = 0;
                        board[i+2][j] = 0;
                        board[i+2][j-1] = 0;
                        answer++;
                    }
                }
            }
        }

        if(temp==answer){
            return false; // 더 이상 지울게 없다
        } else {
            return true;
        }

    }

    public boolean isDeleteOrangeTwo(int[][] board){ // 주황 2번

        int temp = answer;
        for(int i=0;i<=board.length-3;i++){
            for(int j=0;j<=board.length-2;j++){
                if(board[i][j]!=0 && checkTop(board,i,j+1,i+1,j+1)){
                    if(board[i][j]==board[i+1][j] && board[i+1][j] == board[i+2][j] &&
                            board[i+2][j] == board[i+2][j+1]){
                        board[i][j] = 0;
                        board[i+1][j] = 0;
                        board[i+2][j] = 0;
                        board[i+2][j+1] = 0;
                        answer++;
                    }
                }
            }
        }

        if(temp==answer){
            return false; // 더 이상 지울게 없다
        } else {
            return true;
        }

    }

    public boolean isDeleteOrangeThree(int[][] board){ // 주황 3번

        int temp = answer;
        for(int i=0;i<=board.length-2;i++){
            for(int j=2;j<=board.length-1;j++){
                if(board[i][j]!=0 && checkTop(board,i,j-1,i,j-2)){
                    if(board[i][j]==board[i+1][j] && board[i+1][j] == board[i+1][j-1] &&
                            board[i+1][j-1] == board[i+1][j-2]){
                        board[i][j] = 0;
                        board[i+1][j] = 0;
                        board[i+1][j-1] = 0;
                        board[i+1][j-2] = 0;
                        answer++;
                    }
                }
            }
        }

        if(temp==answer){
            return false; // 더 이상 지울게 없다
        } else {
            return true;
        }

    }

    public boolean isBlueOne(int[][] board){ // 주황 3번

        int temp = answer;
        for(int i=0;i<=board.length-2;i++){
            for(int j=1;j<=board.length-2;j++){
                if(board[i][j]!=0 && checkTop(board,i,j-1,i,j+1)){
                    if(board[i][j]==board[i+1][j] && board[i+1][j] == board[i+1][j-1]
                            && board[i+1][j-1] == board[i+1][j+1]){
                        board[i][j] = 0;
                        board[i+1][j] = 0;
                        board[i+1][j-1] = 0;
                        board[i+1][j+1] = 0;
                        answer++;
                    }
                }
            }
        }

        if(temp==answer){
            return false; // 더 이상 지울게 없다
        } else {
            return true;
        }

    }

    public boolean checkTop(int[][] board, int x, int y, int p, int q){

        for(int i=x;i>=0;i--){
            if(board[i][y]!=0){ // 위에 검사 하나라도 0이 아니라면
                return false; // 삭제할 수 없음
            }
        }

        for(int i=p;i>=0;i--){
            if(board[i][q]!=0){
                return false;
            }
        }
        return true; // 삭제 가능

    }
}

4. 결과

 

 

끝.