[알고리즘 문제 풀이🙄] 5656. 벽돌 깨기

📌 문제 요약

구슬을 쏘아 벽돌을 깨트리는 게임을 할 때, 구슬은 N번만 쏠 수 있으며 벽돌들의 정보는 W x H의 배열로 입력된다. 

배열에서의 0은 빈 공간을 의미하며, 구슬이 명중한 벽돌은 상하좌우로 (벽돌에 적힌 숫자 - 1)칸 만큼의 벽돌까지 깨트린다. 

또한 벽돌이 깨지면서 생긴 빈 공간은 중력의 영향으로 아래로 벽돌들이 떨어지며 메워진다고 할 때, N번 구슬을 쏘아 최대한 많은 벽돌을 제거한다면 남은 벽돌의 개수는 얼마인가?

 

🤔 내가 생각한 로직

• 처음 이 문제를 접했을 땐 '예측샷'을 통해 답을 도출하려고 했었다. 한번 구슬을 쏘았을 때 가장 많은 벽돌을 깰 수 있는 열은 열의 합이 가장 큰 것이라고 생각했기 때문이다. 하지만 이렇게 구현하는 경우, 내가 생각한 로직을 완전히 구현했음에도 정확한 답안이 도출되지 않는 문제점이 있었다.
• 먼저 이 문제를 풀었던 친구의 팁을 참고하여 순열 + 완전 탐색으로 구현하는 것이 맞겠다고 생각했다.

 

😥 틀린 코드와 문제점

from copy import deepcopy


# 순서 조합을 만들어 반환
def makeOrder(empty, chance, w):
    global chances
    
    if len(empty) == chance:
        chances.append(empty)
        return
    
    for i in range(w):
        makeOrder(empty + [i], chance, w)


# 입력된 지도에 대해 n번째 열의 시작 행을 찾아 반환
def findStart(arr, n, h):
    for i in range(h):
        if arr[i][n]:
            return i
    return -1


# r: 구슬을 쏘는 지점의 행, l: 구슬을 쏘는 지점의 열, power: 처음 호출 시, 0 입력됨
def breakBrick(r, l, power):
    global breaking

    global chances

    # 현재 지점 정보 기반 power 갱신
    if breaking[r][l] - 1 > power:
        power = breaking[r][l] - 1
    
    breaking[r][l] = 0

    if power < 1:
        return

    for d in directions:
        mi = r + d[0]
        mj = l + d[1]
        
        # 지도 범위 내에 있다면
        if 0 <= mi < H and 0 <= mj < W:
            if chances == [2, 2, 6]:
                print(f'[{mi}, {mj}] 0으로 변경, 남은 power = {power - 1}')
            breakBrick(mi, mj, power - 1)


def gravity(arr, w, h):
    global chance
    cnt = 0
    for i in range(h-1, -1, -1):
        for j in range(w):
            # 벽돌이 있다면 남은 벽돌 수 카운팅 +1
            if arr[i][j]:
                cnt += 1

            # 벽돌이 없는 빈 공간이라면 위에서 한 칸씩 밑으로 내림
            if (not arr[i][j]) and arr[i - 1][j]:
                if i - 1 >= 0:
                    arr[i][j] = arr[i - 1][j]
                    arr[i - 1][j] = 0
                    cnt += 1
    return cnt


# 상 하 좌 우
directions = [[-1, 0], [1, 0], [0, -1], [0, 1]] 

T = int(input())
T = 1

for tc in range(1, T + 1):
    # N: 구슬을 쏘는 횟수, W x H: 벽돌 배열의 크기
    N, W, H = map(int, input().split())

    bricks = [list(map(int, input().split())) for _ in range(H)]
    min_rest = W * H

    chances = []

    makeOrder([], N, W)

    for chance in chances:
        breaking = deepcopy(bricks)

        for c in chance:
            target = findStart(breaking, c, H)
            if target == -1 :
                continue
            breakBrick(target, c, 0)

            if chance == [2, 2, 6]:
                print(f'c = {c}, target = {target}')
                for b in breaking:
                    print(b)
                print()

            # 벽돌 + 중력 효과
            remain = gravity(breaking, W, H)    

            

        min_rest = min(min_rest, remain)
    
    print(f'#{tc} {min_rest}')
   
"""
출력
[0, 0, 0, 0, 0, 0, 0, 0, 0, 0]
[0, 0, 0, 0, 0, 0, 0, 0, 0, 0]
[1, 0, 0, 0, 1, 0, 0, 0, 0, 1]
[0, 0, 0, 0, 0, 1, 0, 0, 0, 9]
[0, 0, 0, 0, 0, 2, 0, 0, 0, 1]
[0, 0, 0, 0, 0, 0, 0, 0, 1, 1]
[0, 0, 0, 0, 0, 0, 0, 0, 1, 1]
[0, 0, 0, 0, 0, 0, 0, 2, 1, 1]
[0, 0, 0, 0, 0, 0, 0, 0, 2, 5]
[0, 0, 0, 0, 0, 0, 0, 0, 1, 1]

#1 0
"""

 

▷ 뻗어나가며 터질 때에도 상하좌우로 모두 터져버린다는 문제점이 있었다.

▷ for d in directions로 재귀 함수를 구성한 것이 오류였다.

 

from copy import deepcopy
from collections import deque


# 순서 조합을 만들어 반환
def makeOrder(empty, chance, w):
    global chances

    if len(empty) == chance:
        chances.append(empty)
        # print(empty)
        return

    for i in range(w):
        makeOrder(empty + [i], chance, w)


# 입력된 지도에 대해 n번째 열의 시작 행을 찾아 반환
def findStart(arr, n, h):
    for i in range(h):
        if arr[i][n]:
            return i
    return -1


# r: 구슬을 쏘는 지점의 행, l: 구슬을 쏘는 지점의 열, power: 처음 호출 시, 0 입력됨
# BFS 사용
def breakBrick(r, l, power):
    global breaking
    queue = deque([[r, l]])

    while queue:
        [r, c] = queue.popleft()

        if breaking[r][c] < 2:
            breaking[r][c] = 0
            continue

        # 벽돌에 적힌 수가 2 이상이면
        power = breaking[r][c]
        breaking[r][c] = 0

        for n in range(1, power):
            for d in directions:
                mi = r + d[0] * n
                mj = c + d[1] * n

                # 지도 범위 내에 있다면
                if 0 <= mi < H and 0 <= mj < W:
                    queue.append([mi, mj])


# 중력에 의해 벽돌들이 아래로 내려오며 빈공간을 메우는 효과
def gravity(w, h):
    global breaking
    cnt = 0
    for j in range(w):
        empty = 0

        for i in range(h - 1, -1, -1):
            # 벽돌이 있다면 남은 벽돌 수에 카운트 + 1
            if breaking[i][j]:
                cnt += 1
                if empty and i + empty < h:
                    breaking[i + empty][j] = breaking[i][j]
                    breaking[i][j] = 0
            # 빈 공간이라면
            elif not breaking[i][j]:
                empty += 1
    return cnt


def check_cnt(bricks):
    cnt = 0
    for i in range(H):
        for j in range(W):
            if bricks[i][j] != 0:
                cnt += 1
    return cnt


# 상 하 좌 우
directions = [[-1, 0], [1, 0], [0, -1], [0, 1]]

T = int(input())

for tc in range(1, T + 1):
    # N: 구슬을 쏘는 횟수, W x H: 벽돌 배열의 크기
    N, W, H = map(int, input().split())

    bricks = [list(map(int, input().split())) for _ in range(H)]
    min_rest = check_cnt(bricks)
    # print(min_rest)
    chances = []

    makeOrder([], N, W)

    for chance in chances:
        remain = 0
        breaking = deepcopy(bricks)
        for c in chance:
            target = findStart(breaking, c, H)
            if target == -1:
                continue
            breakBrick(target, c, 0)

            # 벽돌 깨기 + 중력 효과
            remain = gravity(W, H)

            # 남아 있는 벽돌이 없다면 탈출
        remain = check_cnt(breaking)

        min_rest = min(min_rest, remain)

        # 남아 있는 벽돌이 없다면 종료
        if not remain:
            break

    print(f'#{tc} {min_rest}')

 

▷target을 찾지 못하면 -1을 반환하도록 설계하고, 처음에 remain(남아있는 벽돌 수)을 0으로 초기하였다.

→ 따라서 N번 벽돌 깨기를 시도했을 때, 매번 target을 찾지 못하면 remain이 0인 채로 반복문이 종료되어 남아있는 벽돌이 0이라는 결론으로 해당 테스트 케이스가 마무리되는 문제점 발생했다.

 

🤗 제출 후 pass한 코드

from copy import deepcopy
from collections import deque


# 순서 조합을 만들어 반환
def makeOrder(empty, chance, w):
    global chances

    if len(empty) == chance:
        chances.append(empty)
        return

    for i in range(w):
        makeOrder(empty + [i], chance, w)


# 입력된 지도에 대해 n번째 열의 시작 행을 찾아 반환
def findStart(arr, n, h):
    for i in range(h):
        if arr[i][n]:
            return i
    return -1


# r: 구슬을 쏘는 지점의 행, l: 구슬을 쏘는 지점의 열, power: 처음 호출 시, 0 입력됨
# BFS 사용
def breakBrick(r, l, power):
    global breaking
    queue = deque([[r, l]])

    while queue:
        [r, c] = queue.popleft()

        if breaking[r][c] < 2:
            breaking[r][c] = 0
            continue

        # 벽돌에 적힌 수가 2 이상이면
        power = breaking[r][c]
        breaking[r][c] = 0

        for n in range(1, power):
            for d in directions:
                mi = r + d[0] * n
                mj = c + d[1] * n

                # 지도 범위 내에 있다면
                if 0 <= mi < H and 0 <= mj < W:
                    queue.append([mi, mj])


# 중력에 의해 벽돌들이 아래로 내려오며 빈공간을 메우는 효과
def gravity(w, h):
    global breaking
    cnt = 0
    for j in range(w):
        empty = 0
        for i in range(h - 1, -1, -1):
            # 벽돌이 있다면 남은 벽돌 수에 카운트 + 1
            if breaking[i][j]:
                cnt += 1
                if empty and i + empty < h:
                    breaking[i + empty][j] = breaking[i][j]
                    breaking[i][j] = 0
            # 빈 공간이라면
            elif not breaking[i][j]:
                empty += 1
    return cnt


# 상 하 좌 우
directions = [[-1, 0], [1, 0], [0, -1], [0, 1]]

T = int(input())

for tc in range(1, T + 1):
    # N: 구슬을 쏘는 횟수, W x H: 벽돌 배열의 크기
    N, W, H = map(int, input().split())

    bricks = [list(map(int, input().split())) for _ in range(H)]
    min_rest = W * H

    chances = []

    makeOrder([], N, W)

    for chance in chances:
        remain = float('inf')
        breaking = deepcopy(bricks)
        for c in chance:
            target = findStart(breaking, c, H)
            if target == -1:
                continue
            breakBrick(target, c, 0)

            # 벽돌 깨기 + 중력 효과
            remain = gravity(W, H)

            # 남아 있는 벽돌이 없다면 탈출
            if not remain:
                break

        min_rest = min(min_rest, remain)

        # 남아 있는 벽돌이 없다면 종료
        if not remain:
            break

    print(f'#{tc} {min_rest}')

 

▶ 따라서 남아있는 벽돌을 세는 remain 변수를 처음에 float('inf')로 초기화해주었다.

 

🧐 참고할 코드

다른 친구들의 코드를 참고했지만, 나와 로직이 거의 동일해서 무엇이 문제인지 찾기가 더욱 어려웠다. 결국 내 코드 안에 문제점이 있었다..😞

 

😎 앞으로의 개선 방향

처음에 변수를 초기화할 때, 어떤 값으로 할지를 좀더 꼼꼼히 설계해야겠다고 생각했다. 언제쯤 나는 이 모든 걸 보완해서 문제를 풀 수 있을까..😂