블록 게임

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

class Solution {
    int[][] Board;
    int N;
    boolean canFill(int row, int col){
        for(int i = 0 ; i < row; i++){
            if(Board[i][col] != 0) return false;
        }
        return true;
    }
    boolean find(int row, int col, int h, int w){
        int emptyCnt = 0;
        int lastValue = -1;
        for(int r = row; r < row+h; r++){
            for(int c = col; c < col+w; c++){
                if(Board[r][c] == 0){
                    if(!canFill(r,c)) return false;
                    if(++emptyCnt > 2) return false;
                }else {
                    if(lastValue !=-1 && lastValue!=Board[r][c]) return false;
                    lastValue = Board[r][c];
                }
            }
        }
        
        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) {
        int answer = 0;
        N = board.length;
        Board = board;
        int cnt;
        do{
            cnt = 0;
            for(int i = 0; i < N; i++){
                for(int j = 0 ; j < N; j++){
                    if(i<=N-2 && j<=N-3 && find(i,j,2,3)){
                        cnt++;
                    }else if(i<=N-3 && j<=N-2 && find(i,j,3,2)){
                        cnt++;
                    }
                }
            }
            answer+= cnt;
        }while(cnt != 0);
        return answer;
    }
}

• 서술 : 가로, 세로로 직사각형을 모든 가능한 칸을 반복하여 시행하는데, 만약 도형이 하나 지워지면 새로운 경우를 위해 do while로 경우가 나오지 않을 때까지 무한 반복한다.(처음부터)

  경우를 찾는 것은 현재 칸에서 가로, 세로로 2,3 늘려 직사각형 모양으로 경우를 따진 후, 빈 칸이 2개인지, 같은 숫자로만 구성된(한 도형으로 집힌 직사각형인지)건지, 위에서부터 쭉 내렸을 때, 빈 공간을 채울 수 있는지 체크한다. 모든 조건에 만족하면, 개수를 하나 늘리고 해당 도형을 지워준다.