블록 게임

• 그냥 구현문제. 어떻게든 돌아가게 만드는 것은 어렵지 않지만, 깔끔하게 짜려면 (귀찮은) 시간이 소요된다..
• 처음에 실수했던 부분은, 어떤 블록을 제거할 수 있는지의 여부를 그 블록 위에 다른 블록이 존재하는가로 체크했더니, 이런 예외 케이스에 부딪혔다

  • 11
    12
    12 
     22

    • (2 위에 1이 있지만, 2는 지울 수 있다)
• 그래서 로직을 다르게 바꿔서 작성했다. 보드 전체에 대해서 한번의 스캔으로 계산을 마치므로 시간복잡도는 O(|board|) = O(N^2)이다

"""Solution code for "Programmers 42894. 블록 게임".

- Problem link: https://programmers.co.kr/learn/courses/30/lessons/42894
- Solution link: http://www.teferi.net/ps/problems/programmers/42894
"""

import collections
import operator

EMPTY = 0
BLACK = -1


def can_remove(block, block_coords, board):
    if len(block_coords) != 4:
        return False
    r1 = min(block_coords, key=operator.itemgetter(0))[0]
    r2 = max(block_coords, key=operator.itemgetter(0))[0]
    c1 = min(block_coords, key=operator.itemgetter(1))[1]
    c2 = max(block_coords, key=operator.itemgetter(1))[1]
    for r in range(r1, r2 + 1):
        if any(x not in (BLACK, block) for x in board[r][c1:c2 + 1]):
            return False
    return True


def fill_black(board, r, c):
    board[r][c] = (BLACK if r == 0 or board[r - 1][c] == BLACK else EMPTY)


def solution(board):
    N = len(board)
    removed_count = 0
    coords_by_block = collections.defaultdict(list)
    for r in range(N):
        for c in range(N):
            block = board[r][c]
            if block == EMPTY:
                fill_black(board, r, c)
            else:
                block_coords = coords_by_block[block]
                block_coords.append((r, c))
                if not can_remove(block, block_coords, board):
                    continue
                removed_count += 1
                for block_r, block_c in block_coords:
                    fill_black(board, block_r, block_c)

    return removed_count