[프로그래머스] 블록 게임 / 2019 카카오 블라인드 채용 / python

문제에 주어진 조건들에 맞게 완전 탐색을 하면 된다.

조건들을 정리해보면

• 검은 블록을 채워서 없앨 수 있는 직사각형의 크기는 2x3, 3x2 두 가지이다.
• 위의 크기에 맞는 직사각형을 발견했을 때
  • 6개의 칸에 서로 다른 숫자의 블록이 들어와서는 안 된다.
  • 6개의 칸 중에 빈 블록을 발견했을 때 그 지점으로 부터 필드의 맨 위까지 모두 비어있어야 한다.(검은 블록을 위에서 아래로 떨어트려야 하기 때문)
  • 빈 블록을 채우기 위해 검은 블록을 2개보다 많이 사용하면 안 된다.

필드의 한 지점에서 확인해 볼 직사각형(2x3 또는 3x2)이 필드를 벗어나지 않는 범위 안에서 위의 조건들을 만족한다면 블록을 없앨 수 있다.

(0, 0) 지점부터 필드의 모든 지점을 column 보다 row 우선으로 돌아보면 검은 블록들과 함께 제거할 수 있는 직사각형들을 찾을 수 있다.

여기서 주의해야할 점이 있는데, 필드의 모든 지점을 한 번씩 다 거쳐가며 확인을 했다 해도 제거 가능한 블록들이 남아있을 수도 있다.
바로 아래와 같은 상황일 때다.

feat. 그림판 ㅋㅋ

• column은 위에서 아래로, row는 왼쪽부터 오른쪽으로 확인할 경우, 주황색 맨 위 첫 부분을 만났을 때 2x3 직사각형이 조건을 만족하는지 보자.
• 2x3 범위 안에 파란색 블록이 들어와있어서 조건을 만족하지 못하고 그냥 넘어간다.
• 그 다음으로 마주친 파란색은 3x2 직사각형 조건을 만족함으로 제거한다.
• 이제 주황색 부분도 2x3 직사각형 조건을 만족한다.

이렇게 될 경우 모든 필드를 한 번씩만 돌았을 때 주황색 부분이 조건을 만족하지만 필드에 남아있게 된다.

그렇기 때문에 조건을 만족하는 블록들이 필드에 존재하지 않을 때까지 모든 필드를 도는 것을 반복해야 한다.

def solution(board):
    answer = 0
    removed_rectangle_count = -1

    while removed_rectangle_count != 0:
        removed_rectangle_count = count_removed_rectangle(board)

        answer += removed_rectangle_count

    return answer


def count_removed_rectangle(board):
    y_len, x_len = len(board), len(board[0])
    removed_rectangle_count = 0

    for i in range(y_len):
        for j in range(x_len):
            if is_possible_fill_rectangle(board, i, j, 2, 3):
                remove_filled_rectangle(board, i, j, 2, 3)
                removed_rectangle_count += 1

            if is_possible_fill_rectangle(board, i, j, 3, 2):
                remove_filled_rectangle(board, i, j, 3, 2)
                removed_rectangle_count += 1

    return removed_rectangle_count


def is_possible_fill_rectangle(board, y, x, height, width):
    y_len, x_len = len(board), len(board[0])

    if y + height > y_len or x + width > x_len:
        return False

    before_block_num = -1
    used_black_block_count = 0

    for i in range(y, y + height):
        for j in range(x, x + width):
            if is_empty_block(board, i, j):
                if not is_empty_top_part(board, i, j):
                    return False

                used_black_block_count += 1

                if used_black_block_count > 2:
                    return False
            else:
                if is_different_block(board, i, j, before_block_num):
                    return False

                before_block_num = board[i][j]

    return True


def is_empty_block(board, i, j):
    return True if board[i][j] == 0 else False


def is_different_block(board, i, j, before_block_num):
    return True if before_block_num != -1 and before_block_num != board[i][j] else False


def is_empty_top_part(board, y, x):
    for i in range(y):
        if board[i][x] != 0:
            return False

    return True


def remove_filled_rectangle(board, y, x, height, width):
    for i in range(y, y + height):
        for j in range(x, x + width):
            board[i][j] = 0