231116 - 블록게임(구현문제)

[robert-min]

블록문제

• 풀이 : 주석 참고
• 포인트 : 문제 풀이를 단계적으로 분리한 후 코드 작성

dx = [-1, 1, 0, 0]
dy = [0, 0, -1, 1]

def dfs(board, x, y, board_num, visited) :
    block = [(x, y, 1)]
    n = len(board)
    q = [(x, y)]
    visited[y][x] = True

    while q :
        x, y = q.pop()
        for i in range(4) :
            ax, ay = x + dx[i], y + dy[i]
            if -1 < ax < n and -1 < ay < n and board[ay][ax] == board_num and not visited[ay][ax] :
                block.append((ax, ay, 1))
                visited[ay][ax] = True
                q.append((ax, ay))

    return block

def min_rectangle(board, board_num, block) :
    x_list = sorted([ coord[0] for coord in block ])
    y_list = sorted([ coord[1] for coord in block ])

    for i in range(y_list[0], y_list[-1]+1) :
        for j in range(x_list[0], x_list[-1]+1) :
            if board[i][j] != board_num :
                block.append((j, i, 0))

def find_blocks(board):
    n = len(board)
    visited = [[False]*n for _ in range(n)]
    block_list = list()
    for i in range(n) :
        for j in range(n) :
            if not visited[i][j] and board[i][j] :
                # 2 블록 탐색
                block = dfs(board, j, i, board[i][j], visited)
                # 3 직사각형 좌표 탐색
                min_rectangle(board, board[i][j], block)
                block_list.append(block)

    return block_list

def is_block_enable(board, block) :
    for x, y, check in block :
        if check == 1 :
            continue
        for i in range(y, -1, -1) :
            if board[i][x] != 0 :
                return False
    return True

def check_all_blocks(board, block_list) :
    if not block_list :
        return 0, []

    n = len(board)
    block_num = len(block_list)
    new_block_list = list()
    cnt = 0

    for idx, block in enumerate(block_list) :
        # 5. 블럭이 지워지는지 확인
        if is_block_enable(board, block) :
            for x, y, _ in block :
                board[y][x] = 0
            cnt += 1
            continue
        new_block_list.append(block)

    return cnt, new_block_list

def solution(board):
    # 1. 모든 블록 탐색
    block_list = find_blocks(board)
    answer = 0
    while True :
        # 4. 모든 블록 탐색(앞에서 지워졌을 때 다른 블록이 지워질 수 있으니 cnt == 0 일때까지 반복
        cnt, block_list = check_all_blocks(board, block_list)
        answer += cnt
        if cnt == 0 :
            break

    return answer