[Algorithm] 프로그래머스 - 블록게임

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

접근

블록의 모양이 12가지이다. 이 중에 지울 수 있는 블록의 모양은 5개뿐이다.

또한, 그 블록을 만들기 위해 필요한 1x1 크기의 블록의 갯수는 4개이다.

이를 고려하면, 각 블록의 검사 기준 위치에서 지울 수 있는 5개의 블록을 모두 검사하면 문제를 해결할 수 있다.

검사 기준 위치는 각 블록의 최상단 최우측이다. 내가 블록을 좌측에서 우측으로 움직일 것이기 때문이다.

이 검사 기준 위치를 기반으로 검사 배열을 정의한다.

검사 배열은 검사 기준 위치에서 검사하려는 블록의 모든 1x1 블록에 접근하게 할 수 있는 변화량이다.

나는 좌측에서 우측으로 하나씩 1x1 크기의 검은 블록을 떨어트릴 것이다.

그리고 검사 기준에 부합하면 그 블록을 바로바로 지울 것이고, 다시 이 작업을 반복할 것이다. 단, 반복 하기 전 임시로 떨어트린 검은 블록은 초기화한다.

하지만, 이 때 주의해야 할 점이 하나 있다.

높이가 2인 블록은 이 방법이 유효하지만, 높이가 3인 블록은 이 방법이 유효하지 않다.

높이가 2인 블록은 좌측에서 우측으로 블록을 하나씩만 떨어트려도 (지울 수 있는 블록에 한하여 )검사 기준에 부합하는 경우가 반드시 존재하지만, 높이가 3인 블록은 같은 열에 대해 검은 블록을 하나 떨어트린 상태에서 하나 더 떨어트려야 검사 기준에 부합하기 때문이다.

이를 해결하기 위해, 좌측에서 우측으로 검은 블록을 떨어트리는 작업을 두 번 반복 후 기존 작업을 반복한다.

소스코드(Java)

import java.util.*;

class Solution {

    int[][][] types =  {
            { {0,-2}, {0,-1}, {1,-2}, {1,-1}, {1,0} },
            { {1,0}, {2,0}, {0,1}, {1,1}, {2,1} },
            { {1,0}, {0,-1}, {1,-1}, {2,-1}, {2,0} },
            { {0,-1}, {0,1}, {1,-1}, {1,0}, {1,1} },
            { {0,-2}, {0,-1}, {1,-2}, {1,-1}, {1,0} }
        };

    private int get(int[][] board, int y, int x) {
        if(y >= board.length || y < 0) return -1;
        if(x >= board[0].length || x < 0) return -1;
        return board[y][x];
    }

    public int solution(int[][] board) {

        int result = 0;
        boolean removed;

        do {
            removed = false;
            for(int h = 0; h < 2; h++) {
                for(int j = 0; j < board[0].length; j++) {
                    for(int i = 0; i < board.length; i++) {

                        if(board[i][j] != 0) break;
                        if(get(board, i+1, j) != 0) board[i][j] = -2;

                        for(int k = 0; k < types.length; k++) {

                            Map<Integer, Integer> hs = new HashMap<>();

                            for(int l = 0; l < types[0].length; l++) {
                                int type = get(board, i+types[k][l][0], j+types[k][l][1]);
                                hs.put(type, hs.getOrDefault(type, 0)+1);
                            }

                            if(hs.containsKey(0) || hs.containsKey(-1)) continue;

                            if(hs.getOrDefault(-2, 0) == 1 && hs.size() == 2) {
                                result += 1;
                                removed = true;
                                for(int l = 0; l < types[0].length; l++) {
                                    board[i+types[k][l][0]][j+types[k][l][1]] = 0;
                                }
                                board[i][j] = 0;
                                break;
                            }
                        }
                    }
                }
            }
            for(int y = 0; y < board.length; y++) {
                for(int x = 0; x < board[0].length; x++) {
                    if(board[y][x] == -2) board[y][x] = 0;
                }
            }
        } while(removed);

        return result;

    }
}