[알고리즘] 벽돌 깨기

벌써 블로그 방문자 수 700명이라니 부족한 글을 봐주시는 여러분들께 감사의 말씀드립니다. 

포인트

• 이번 포인트는 잘 구현을 할 수 있는 가? 입니다.

        for j in range(w):  # 맵을 돌면서
            for i in range(h - 1, -1, -1):
                row = i  # 맨 아래에서 시작
                # 아래로 땡겨오는 코드 이니 잘보면 좋다
                while row >= 1 and copy_data[row][j] == 0:
                    row -= 1

                if row != i:
                    copy_data[i][j] = copy_data[row][j]
                    copy_data[row][j] = 0

다른 부분들도 포인트가 많지만 오늘은 이 포인트가 제일 중요한 것 같습니다. 어떻게 위에 있는 1들을 아래로 땡겨 오는가? 사실 이 부분들을 고민하긴 했었는데

간단히 말하면 
"제일 아래에서 시작해서 1인 부분을 찾아 아래서 부터 바꿔 준다" 라고 저는 이해했습니다. 

 

🧶문서는 항상 수정 될 수 있습니다. 비판은 환영합니다. 

python

import copy
from collections import deque


def boundary(x: int, y: int) -> bool:
    if 0 <= x < w and 0 <= y < h:
        return True
    return False


def remove_block(col: int, copy_data: list) -> None:
    q = deque()
    row = 0

    while boundary(col, row) and copy_data[row][col] == 0:
        row += 1

    if row == h:  # 만약 벽에 부딛치면 종료
        return

    q.append([col, row])

    while q:
        x, y = q.popleft()
        k = copy_data[y][x]
        copy_data[y][x] = 0
        for i in range(4):

            for temp in range(1, k):  # 4 방향 일직선으로 넘어간다
                nx = x + temp * dx[i]
                ny = y + temp * dy[i]

                if not (0 <= nx < w and 0 <= ny < h):
                    continue
                # 범위를 넘어가면 종료

                q.append([nx, ny])


def shot() -> int:
    copy_data = copy.deepcopy(data)
    # 2차원 배열 복사

    for k in range(n):
        remove_block(sel[k], copy_data)
        # 블록을 없애준다

        for j in range(w):  # 맵을 돌면서
            for i in range(h - 1, -1, -1):
                row = i  # 맨 아래에서 시작
                # 아래로 땡겨오는 코드 이니 잘보면 좋다
                while row >= 1 and copy_data[row][j] == 0:
                    row -= 1

                if row != i:
                    copy_data[i][j] = copy_data[row][j]
                    copy_data[row][j] = 0

                # 맨 위에서 시작해서 1이 나올깨까지 행을 줄이고
                # 1이 나오면 바꾸고 그곳은 0으로 표시한다.

    cnt = 0
    for i in range(h):
        for j in range(w):
            if copy_data[i][j] != 0:
                cnt += 1

    return cnt


def go(index) -> None:
    global count
    if index == n:
        result = shot()
        count = min(count, result)
        return

    for i in range(w):
        sel.append(i)
        go(index + 1)
        sel.pop()

        if count == 0:
            return


for test in range(1, int(input()) + 1):
    n, w, h = map(int, input().split())

    data = [list(map(int, input().split())) for _ in range(h)]
    # 우, 좌, 하, 상
    dx = [1, -1, 0, 0]
    dy = [0, 0, 1, -1]
    sel = []
    # 벽돌개수의 최고값 부여
    count = 987654321

    go(0)

    print('#{} {}'.format(test, count))