SW Expert Academy 5656. [모의 SW 역량테스트] 벽돌 깨기 풀이 With Python

문제 링크: https://swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AWXRQm6qfL0DFAUo&categoryId=AWXRQm6qfL0DFAUo&categoryType=CODE

SW Expert Academy

먼저 벽돌을 깨었을 때, 빈 공간이 있을 경우 벽돌을 아래로 떨어뜨리는 함수인 clean함수와 x, y지점의 벽돌을 부술 때 깨진 벽돌 개수와 깨진 맵의 상태를 반환하는 함수인 destroy함수와 dfs방식으로 탐색하고, 문제에서 주어진 횟수 n번의 벽돌을 깨는 것을 실행하는 solution함수로 이 문제를 해결하였다. 

from copy import deepcopy


def clean(map1, h, w):
    map2 = deepcopy(map1)
    for y in range(w):
        for x in range(h):
            if map2[x][y] == 0:
                for j in range(x, 0, -1):
                    map2[j][y] = map2[j - 1][y]
                map2[0][y] = 0
    return map2


def destroy(map1, h, w, x, y):
    counter = 0
    dx = [-1, 0, 1, 0]
    dy = [0, -1, 0, 1]
    map2 = deepcopy(map1)
    s1 = [[x, y]]
    while s1:
        nx, ny = s1.pop()
        number = map2[nx][ny]
        if map2[nx][ny] == 0:
            continue
        map2[nx][ny] = 0
        counter += 1
        if number > 1:
            for i in range(1, number):
                for d in range(4):
                    nx2 = nx + i * dx[d]
                    ny2 = ny + i * dy[d]
                    if -1 < nx2 < h and -1 < ny2 < w and map2[nx2][ny2] != 0:
                        s1.append([nx2, ny2])
    return map2, counter


def solution(map1, n, h, w):
    global blocks
    answer = h * w
    # 공 횟수 깨뜨린 블럭 맵
    stack = [[0, 0, map1]]
    while stack:
        count, sub, nmap = stack.pop()
        if sub==blocks:
            return 0
        if count == n:
            if answer > blocks - sub:
                answer = blocks - sub
        else:
            # y축 전부 돌면서
            for y1 in range(w):
                flag = 0
                x1 = 0
                while 1:
                    if x1 == h:
                        flag = 1
                        break
                    elif nmap[x1][y1] == 0:
                        x1 += 1
                    else:
                        break
                if flag == 1:
                    continue
                else:
                    nmap2, nsub = destroy(nmap, h, w, x1, y1)
                    nmap2=clean(nmap2,h,w)
                    stack.append([count + 1, sub + nsub, nmap2])
    return answer

t=int(input())
for test in range(1,t+1):
    n, w, h = map(int, input().split())
    map1 = []
    blocks = 0
    for _ in range(h):
        s = list(map(int, input().split()))
        for i in s:
            if i != 0:
                blocks += 1
        map1.append(s)
    answer=solution(map1,n,h,w)
    print('#{} {}'.format(test, answer))