블록 게임

programmers.co.kr/learn/courses/30/lessons/42894

코딩테스트 연습 - 블록 게임

from collections import defaultdict

def solution(board):
 # {블록 이름 : 블록 좌표들}, {위에 있는 블록 : 아래에 있는 블록}, 지울 수 없는 모양의 블록
    blocks, bGraph, cannotRemove = defaultdict(list), defaultdict(list), []
    for y in range(len(board)): # 블록 마다 좌표들 구하기
        for x in range(len(board[0])):
            if board[y][x] != 0:
                blocks[board[y][x]].append((y, x))

    for b in blocks: # 가장 아래에 있는 블록이 1개이면 애초에 지울 수 없는 모양의 블록
        blocks[b].sort(key=lambda x: -x[0]) # y좌표로 정렬
        if blocks[b][0][0] != blocks[b][1][0]: 
            cannotRemove.append(b) 
    
    col_board = [[board[y][x] for y in range(len(board))] for x in range(len(board[0]))]
    for col in col_board: # board 세로로 탐색
        upper = [] # 해당 col에서 현재 까지 위에 나타난 블록들
        for b in col: 
            if b != 0: # 해당 col에 있는 블록
                for up in upper: # 위에 있는 블록이 블록 b의 선행 블록이면 bGraph에 추가
                    if b not in bGraph[up] and col.count(b) == 1 and b != up:
                        bGraph[up].append(b)
                if b not in upper: # 블록 b도 위에 있는 블록에 추가
                    upper.append(b)
    
    def search_cannot_B(block): # 해당 블록이 지워지지 않을 경우, 연쇄적으로 지우지 못하는 블록 탐색
        for below in bGraph[block]:
            if below not in cannotRemove:
                cannotRemove.append(below)
                search_cannot_B(below) # 연쇄적으로 탐색하기 위해 재귀 사용

    for cannot in cannotRemove[:]: # 애초에 지울 수 없는 블록들
        search_cannot_B(cannot) # 이 블록들 때문에 연쇄적으로 지울 수 없는 블록들 탐색
    
    return len(blocks) - len(cannotRemove) # 전체 블록 수 - 지울 수 없는 블록 수

→ 어떤 column에서 블록들이 연속적으로 등장할 때, 아래쪽에 있는 어떤 블록이 해당 column에서 1칸만 존재할때만

위에 있는 블록이 선행 블록이 된다. 

 

실제 게임 진행 순서대로 풀지 못하고 규칙성을 통해서만 해결한것 같아서 나중에 다시 풀어봐야겠다..