[프로그래머스] 블록 게임(Python)

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

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

구현이 좀 까다로웠던 문제다.

 

처음에 블록 게임을 테트리스처럼 생각해서 헷갈렸는데 검정 블록은 아래로 쭉 가는 방향으로만 쌓을 수 있다.

1. 매번 루프마다 전체 블록판을 서치 하면서 블록들의 모양을 찾음

2. 동시에 검정 블록을 쌓을 수 있는 위치도 업데이트

3. 모양을 찾고 블록마다 빈 공간의 위치(채우면 제거할 수 있는 위치들)를 찾아서 업데이트

4. 해당 루프마다 블록을 제거할 수 있으면 다시 서치하고 제거할 수 없다면 현재까지 제거된 횟수 반환

 

서치 효율을 향상시키기 위해 set과 dict 자료형을 활용해서 풀었다.

 

나의 풀이

# 각 블록마다 비어있는 공간 찾는 함수
def check_diff(lst):
    row = set()
    col = set()
    for r, c in lst:
        if r not in row:
            row.add(r)
        if c not in col:
            col.add(c)
    answer = []
    for r in row:
        for c in col:
            if (r,c) not in lst:
                answer.append((r,c))
    return answer

# 제거할 수 있는지 확인하는 함수
def can_del(lst,black):
    for block in lst:
        if block not in black:
            return False
    return True        

def solution(board):
    N = len(board)
    answer = 0
    updated = True
    while updated:
        block_info = {}
        black = set()
        check = [False for _ in range(N)]
        for i in range(N):
            for j in range(N):
                typed = board[i][j]
                if typed != 0:
                    if typed in block_info:
                        block_info[typed][0].append((i,j))
                    else:
                        block_info[typed] = [[(i,j)],list()]
                    check[j] = True
                else:
                    if not check[j]:
                        black.add((i,j))
        for typed in block_info:
            block_info[typed][1] = check_diff(block_info[typed][0])

        updated = False
        for typed in block_info:
            if can_del(block_info[typed][1],black):
                # 삭제 가능
                answer +=1
                updated = True
                for i,j in (block_info[typed][0] + block_info[typed][1]):
                    board[i][j] = 0
    return answer