알고리즘(블록 게임)

[블록 게임]

 

* 로직

• 문제에 주어진 블록을 직사각형으로 채우게 된다면 사이즈는 2*3 or 3*2 형태가 된다
• (0,0)부터 기준점을 한 칸씩 옮기면서 2*3인 경우와 3*2인 경우를 고려한다
• 해당 사이즈만큼 탐색하면서 값이 0인 곳에서는 검은 블록을 위에서부터 떨어뜨릴 수 있는지 확인한다
  • 만약 중간에 다른 블록이 있다면 불가능
  • 없다면 가능
  • 검은 블록을 사용한 개수를 카운팅한다
• 해당 사이즈만큼 탐색하면서 만약 검은 블록의 개수를 2개 초과한 경우엔 불가능 처리를 한다
  (주어진 블록들의 개수는 항상 4개이기 때문에 -> 6 - 2 = 4)
  
  
• 검은 블록의 개수까지 만족한다면 해당 사이즈만큼의 값은 0으로 갱신한다
• 위 과정을 반복하며, 만약 모든 기준점들을 다 돌았을때 제거된 블록이 하나도 없다면 종료한다

 

//블록게임
public class Problem_BlockGame {
    static int N;

    public static void main(String[] args) {
        int[][] board = {
                {0,0,0,0,0,0,0,0,0,0},{0,0,0,0,0,0,0,0,0,0},{0,0,0,0,0,0,0,0,0,0},{0,0,0,0,0,0,0,0,0,0},
                {0,0,0,0,0,0,4,0,0,0},{0,0,0,0,0,4,4,0,0,0},{0,0,0,0,3,0,4,0,0,0},{0,0,0,2,3,0,0,0,5,5},
                {1,2,2,2,3,3,0,0,0,5},{1,1,1,0,0,0,0,0,0,5}
        };

        int answer = solution(board);
        System.out.println(answer);
    }

    public static int solution(int[][] board) {
        int answer = 0;
        N = board.length;

        //0,0부터 기준점 이동하면서 -> 2*3 or 3*2로 잘라서 가능성 비교 -> 가능하다면 지우고 & cnt++
        while (true){
            int cnt = 0;
            for(int i=0; i<N; ++i){
                for(int j=0; j<N; ++j){
                    if(isPossible(i, j, board)){
                        cnt++;
                    }
                }
            }
            if(cnt == 0) break;
            answer += cnt;
        }

        return answer;
    }

    private static boolean isPossible(int y, int x, int[][] board) {
        //2*3 사이즈로 자르는 경우
        int rowSize = 2;
        int colSize = 3;
        if(cropBoard(rowSize, colSize, y, x, board)){

            //제거하기
            removeBlock(rowSize, colSize, y, x, board);
            return true;
        }

        //3*2 사이즈로 자르는 경우
        rowSize = 3;
        colSize = 2;
        if(cropBoard(rowSize, colSize, y, x, board)){
            removeBlock(rowSize, colSize, y, x, board);
            return true;
        }

        return false;
    }

    private static void removeBlock(int rowSize, int colSize, int y, int x, int[][] board) {
        for(int i=0; i<rowSize; ++i){
            for(int j=0; j<colSize; ++j){
                board[y+i][x+j] = 0;
            }
        }
    }

    private static boolean dropBlackBlock(int y, int x, int[][] board) {
        for(int i=0; i<y; ++i){
            if(board[i][x] > 0) return false;
        }
        return true;
    }

    private static boolean cropBoard(int rowSize, int colSize, int y, int x, int[][] board) {
        int base = 0;
        int blackBlockCnt = 0;
        for(int i=0; i<rowSize; ++i){
            int moveY = y + i;
            for(int j=0; j<colSize; ++j){
                int moveX = x + j;

                if(!isRanged(moveY, moveX)) return false;
                if(board[moveY][moveX] == 0) {

                    //검은 돌을 넣을 수 있는지 판단
                    if(!dropBlackBlock(moveY, moveX, board)) {
                        return false;
                    }
                    blackBlockCnt++;
                }

                else if(board[moveY][moveX] > 0){
                    //다른 도형이 존재한다면
                    if(base != 0 && base != board[moveY][moveX]) return false;
                    base = board[moveY][moveX];
                }
            }
        }

        if(base == 0 || blackBlockCnt > 2) return false;
        return true;
    }

    private static boolean isRanged(int y, int x) {
        if(y>=0 && y<N && x>=0 && x<N) return true;
        return false;
    }
}