[SWEA][Python] 5656 벽돌깨기

로직이 완전 깔끔하지는 못하지만 시간 내에 통과하도록 최소한의 연산을 하도록 노력함.

 

기본적으로 재귀를 통해 폭탄을 한발씩 떨어뜨리는 함수,

폭탄이 블록과 만나면 연쇄 폭발을 일으키는 재귀함수

폭발 후 빈칸에 블록을 중력을 적용해 채우는 함수.

 

3가지 함수와

 

남은 블록을 카운팅해주는 함수

 

1개의 함수 총 4개의 함수로 구성했으며

중간에 블록이 모두 터졌을 경우 바로 종료하지는 못했으나

더이상 N을 파고들지 않아도 W를 0~ W-1까지 순회해서 continue로 넘어가게 만듦.

모두 터지지 않을 경우의 로직은 효율적으로 짰다고 생각함.

 

def delete_block(board, x, y, cnt):
    board[x][y] = 0
    if cnt > 1:
        for i in range(1, cnt):
            for dx, dy in delta:
                nx, ny = x + dx * i, y + dy * i
                if 0 <= nx < H and 0 <= ny < W:
                    if board[nx][ny] > 1:
                        delete_block(board, nx, ny, board[nx][ny])
                    board[nx][ny] = 0


def down_block(board):
    new_board = [[0] * W for _ in range(H)]
    for w in range(W):
        init = H - 1
        for h in range(H - 1, -1, -1):
            if board[h][w]:
                new_board[init][w] = board[h][w]
                init -= 1
    return new_board


def count_block(matrix):
    global min_cnt
    cnt = 0
    for i in range(H):
        for j in range(W):
            if matrix[i][j]:
                cnt += 1
    min_cnt = min(min_cnt, cnt)


def game_start(matrix, N):
    if N == 0:
        count_block(matrix)
        return
    # 각 시작마다 배열 복사
    for drop in range(W):
        board = [row[:] for row in matrix]
        x, y = 0, drop
        while x < H and not board[x][y]:
            x += 1
        if x == H:
            count_block(board)
            continue
        delete_block(board, x, y, board[x][y])
        board = down_block(board)
        game_start(board, N - 1)


for test in range(1, int(input()) + 1):
    N, W, H = map(int, input().split())
    matrix = [list(map(int, input().split())) for _ in range(H)]
    delta = ((0, 1), (1, 0), (-1, 0), (0, -1))
    min_cnt = float('inf')
    game_start(matrix, N)
    print(f'#{test} {min_cnt}')