[SWEA] 5656. 벽돌 깨기

https://swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AWXRQm6qfL0DFAUo 

SW Expert Academy

작년에 이 문제를 봤을 때는 못 풀고 넘어갔는데 이번에는 1시간도 안 걸려서 풀었다! 최적화는 제대로 못하긴 했지만.. 모든 기능을 여러 함수로 쪼개 구현해서 overhead가 심하고 메모리 사용이 많다. 풀었다는 것.... 성장했다는 것에 의의를 두는 문제.. deepcopy 없어도 풀 수 있을 것 같긴한데 나중에 더 생각해 봐야겠다.

 

solve() 함수는 구슬을 쏘는 모든 경우의 수를 재귀로 탐색하는 함수이며, 구슬을 쏜 횟수가 n번이면 모든 맵을 탐색하며 벽돌 개수를 세어 최소 벽돌 개수를 갱신한다.

 

bomb() 함수는 벽돌이 저장된 리스트와 구슬을 쏜 열을 받아서, 벽돌이 나타날 때 까지 구슬의 위치 행을 증가시킨다. 벽돌을 만나면 0으로 바꾸주며 파괴시키는데, 파괴시키기 전에 벽돌에 적힌 숫자가 1보다 크면 q에 담아준다. 이 q는 연쇄적으로 파괴시켜야하는 1보다 큰 벽돌들의 위치와 벽돌정보를 담아주는 큐이다. 큐가 빌 때까지 while문을 돌며 상하좌우의 벽돌들을 부수고, 또 연쇄적으로 파괴시킬 벽돌이 나타나면 q에 추가한다. 모든 벽돌을 깨면 while문을 탈출하고, 벽돌이 모두 부숴진 상태를 반환한다.

 

gravity() 함수는 벽돌이 저장된 리스트를 받아서 중력을 적용시킨다. 이전에 풀었던 상어중학교에서 중력을 적용하는 것과 똑같다.

 

from copy import deepcopy
from collections import deque


def bomb(my_brick, bomb_j):
    new_brick = deepcopy(my_brick)
    q = deque()
    for bomb_i in range(h):
        if new_brick[bomb_i][bomb_j] :
            if new_brick[bomb_i][bomb_j] > 1:
                q.append((bomb_i, bomb_j, new_brick[bomb_i][bomb_j]))
            new_brick[bomb_i][bomb_j] = 0
            break

    while q:
        y, x, bn = q.popleft()
        for dy, dx in [(1, 0), (-1, 0), (0, 1), (0, -1)]:
            for k in range(1, bn):
                ny = y + dy*k
                nx = x + dx*k
                if 0 <= ny < h and 0 <= nx < w:
                    if new_brick[ny][nx] > 1:
                        q.append((ny, nx, new_brick[ny][nx]))
                    new_brick[ny][nx] = 0

    return new_brick


def gravity(gravity_brick):
    new_brick = deepcopy(gravity_brick)
    for g_i in range(h-2, -1, -1):
        for g_j in range(w):
            if new_brick[g_i][g_j] and new_brick[g_i+1][g_j] == 0:
                ny = 0
                flag = 0
                for k in range(g_i+1, h):
                    ny = k
                    if new_brick[k][g_j]:
                        flag = 1
                        break
                if flag:
                    new_brick[ny-1][g_j] = new_brick[g_i][g_j]
                else:
                    new_brick[ny][g_j] = new_brick[g_i][g_j]
                new_brick[g_i][g_j] = 0
    return new_brick


def solve(cnt, my_brick):
    global answer
    if cnt == n:
        brick_cnt = 0
        for i in range(h):
            for j in range(w):
                if my_brick[i][j]:
                    brick_cnt += 1
        answer = min(brick_cnt, answer)
        return

    for i in range(w):
        new_brick = bomb(my_brick, i)
        new_brick = gravity(new_brick)
        solve(cnt+1, new_brick)


for tc in range(1, int(input())+1):
    n, w, h = map(int, input().split())
    brick = [list(map(int, input().split())) for _ in range(h)]
    answer = w*h + 1
    solve(0, brick)
    print('#{} {}'.format(tc, answer))