2019 KAKAO BLIND RECRUITMENT : 블록 게임

https://programmers.co.kr/learn/courses/30/lessons/42894

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

 

// 코드

import java.util.*; 
 
 
class Solution {
    
    // board를 편하게 사용하기 위해 멤버로 빼준다.
    int[][] Board;
    // board의 길이
    int N;
    
    
    // canFill : 채울 수 있는지 체크, 있으면 : true, 없다면 : false
    boolean canFill(int row, int col) {        
        for(int i=0; i<row; ++i) if(Board[i][col] != 0) return false;
        return true;        
    }
    
    // find : 지울수 있으면 true, 없으면 false를 반환한다.
    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;
                    // 빈 공간이 2개를 넘어서는지 체크
                    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;        
    }
    
    
    // main
    public int solution(int[][] board) {
        
        Board = board;
        N     = board.length;
        // 답
        int answer = 0;
        // 없앤 블록의 개수
        int cnt;
        
        // [접근법]
        // 0행 0열부터 시작해서 
        // (2*3), (3*2) 크기의 직사각형의 범위 안에서 지워지는지를 체크해나간다.
        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;
    }
}