[2019 KAKAO BLIND RECRUITMENT] 블록 게임

문제

• NxN 보드 위에 블록들이 배치된 채로 게임이 시작된다. 
• 플레이어는 1x1 크기의 검은 블록을 떨어뜨려 쌓을 수 있다.
• 검은 블록과 기존에 놓인 블록을 합해 속이 꽉 채워진 직사각형을 만들 수 있다면 그 블록을 없앨 수 있다.
• 검은 블록을 떨어뜨려 없앨 수 있는 블록 개수의 최댓값을 구하라
• 4 <= N <= 50

 

풀이

• 블록이 주어지고 직사각형으로 채울 수 있으면 해당 블록을 없앨 수 있다.
• 1) 블록 추출하기 -> 번호 별로 딕셔너리에 저장하기
• 2) 블록별로 제거할 수 있는지 확인하기
  • 직사각형 모양을 가정했을 때, 채워야할 빈칸의 인덱스 찾기
    -> 해당 인덱스가 위에서 블록을 떨어드릴 수 있는 자리인지 확인하기
  • 위에서 블록이 막고 있는지 확인하기

 

1,2,5,8,9,18,20 번만 통과 (35점)
-> 블록을 제거하는 순서에 따른 변화가 있을 것으로 예상됨

from collections import defaultdict

# 직사각형 만들 수 있는지 확인
def check_form(block, blank) :
    for b in blank :
        if (b[0]-1, b[1]) in block :
            return False
    return True

# 위에서 조각 떨어뜨릴 수 있는지 확인
def check_up(board, blank) :
    for b in blank :
        for x in range(b[0]+1) :
            if board[x][b[1]] != 0 : 
                return False
    return True


def solution(board):
    N = len(board)
    # 블록 추출하기
    blocks = defaultdict(list)
    for i in range(N) :
        for j in range(N) :
            if board[i][j] != 0 :
                blocks[board[i][j]].append((i, j))

    # 블록별 제거할 수 있는지 확인
    answer = 0

    for k in blocks :
        blocks[k].sort()
        sx, sy = blocks[k][0][0], min(blocks[k][0][1], blocks[k][1][1])
        lx, ly = blocks[k][-1][0], max([y for (x, y) in blocks[k]])

        # 1) 채워야 할 자리 확인
        blank = []
        for i in range(sx, lx+1) :
            for j in range(sy, ly+1) :
                if (i, j) not in blocks[k] :
                    blank.append((i, j))

        # 2) 직사각형 만들 수 있는지 확인
        if not check_form(blocks[k], blank) :
            continue

        # 3) 위에서 조각 떨어뜨릴 수 있는지 확인
        if check_up(board, blank) :
            # 블럭 제거하기
            for (i, j) in blocks[k] :
                board[i][j] = 0
            answer += 1

    return answer

 

 

풀이 2

• 왼쪽에서부터 확인하게 되면 아래와 같은 반례가 존재한다.

[[0, 0, 0, 0, 0], 
 [1, 0, 0, 2, 0], 
 [1, 2, 2, 2, 0], 
 [1, 1, 0, 0, 0], 
 [0, 0, 0, 0, 0]]
 
 # 답 : 2

 

• 어떤 블록을 제거하지 못한다고 확정짓는 경우는 아래와 같다. 
  • 1. 직사각형을 만들 수 없는 형태
  • 2. 제거 못하는 블록이 가로막은 경우
• 제거 못하는 블록의 번호를 impossible 에 저장하고, 
  A 블록을 가로막는 블록 B가 impossible에 속해있다면 A도 impossible에 추가하고
  블록 B가 impossible에 속해있지 않다면 A를 추후 다시 확인하도록 한다. (블록 B가 제거될 수도 있음)

 

10, 17번 추가 통과해서 45점
-> 어디가 문제일까...? ***다시 생각해보기

from collections import defaultdict
from collections import deque

# 직사각형 만들 수 있는 형태인지 확인
def check_form(block, blank) :
    for b in blank :
        if (b[0]-1, b[1]) in block :
            return False
    return True

# 위에서 조각 떨어뜨릴 수 있는지 확인
def check_up(board, blank) :
    for b in blank :
        for x in range(b[0]+1) :
            if board[x][b[1]] != 0 :
                return board[x][b[1]]
    return 0

def solution(board):
    N = len(board)
    # 블록 추출하기
    blocks = defaultdict(list)
    for i in range(N) :
        for j in range(N) :
            if board[i][j] != 0 :
                blocks[board[i][j]].append((i, j))
                
    # 블록별 제거할 수 있는지 확인
    answer = 0
    impossible = set()                  # 제거 불가능한 블록
    keys = deque(list(blocks.keys()))   # 확인해야할 블록 리스트

    while keys :
        k = keys.popleft()
        blocks[k].sort()
        sx, sy = blocks[k][0][0], min(blocks[k][0][1], blocks[k][1][1])
        lx, ly = blocks[k][-1][0], max([y for (x, y) in blocks[k]])
        
        # 1) 채워야 할 자리 확인
        blank = []
        for i in range(sx, lx+1) :
            for j in range(sy, ly+1) :
                if (i, j) not in blocks[k] :
                    blank.append((i, j))

        # 2) 직사각형 만들 수 있는 형태인지 확인
        if not check_form(blocks[k], blank) :
            impossible.add(k)
            continue

        # 3) 위에서 조각 떨어뜨릴 수 있는지 확인
        res = check_up(board, blank)
        if res == 0:             # 블럭 제거하기
            for (i, j) in blocks[k] :
                board[i][j] = 0
            answer += 1
        elif res in impossible : # 제거 불가능
            impossible.add(k)
        else :                   # 다시 확인하기
            keys.append(k)

    return answer

 

 

 

References

•