[SWEA/Python] 5656. 벽돌 깨기

 

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

SW Expert Academy

• 처음에 설계를 제대로 하지 못해서 코드가 많이 난잡해졌다.
• dfs와 bfs를 통한 완전탐색을 진행해서 시간과 메모리를 많이 사용했으나 다행히 pass

from collections import deque
import copy
TC = int(input())

for tc in range(1,TC+1):
    N,W,H = map(int,input().split())
    arr = [list(map(int,input().split())) for _ in range(H)]
    combo = []
    path = [''] * N
    result = []

    def dfs(level):
        global combo,path

        if level == N:
            tmppath = copy.deepcopy(path)
            combo.append(tmppath)
            return

        for i in range(W):
            path[level] = i
            dfs(level+1)

    dfs(0) # 1. dfs를 통해 N개까지의 중복순열을 combo에 저장
    
    def bfs(y,x): 
        global acc

        q = deque([(y,x,acc[y][x])])
        directy = [-1,1,0,0]
        directx = [0,0,-1,1]

        while q:
            y,x,tmp = q.popleft() # 4. tmp에 acc 좌표의 값을 넣어줌
            acc[y][x] = 0

            for k in range(4):
                dy = directy[k] + y
                dx = directx[k] + x

                for l in range(tmp-1): # 5. tmp만큼 상하좌우 이동하면서 벽을 부숨
                    if dy >= H or dy < 0 or dx >= W or dx < 0: # 5-1. 배열인덱스를 벗어나면 continue
                        continue
                    if acc[dy][dx] > 1: # 6. 벽을 부수는 길에 1 이상의 숫자가 있으면 ( 연쇄적으로 부술 수 있는 벽돌이 있다면 )
                        q.append([dy,dx,acc[dy][dx]]) # 6-1. q에 추가

                    acc[dy][dx] = 0
                    dy = directy[k] + dy
                    dx = directx[k] + dx

        drop = [[0]*W for _ in range(H)] # 7. 벽을 부수고 난 후 drop이란 임시배열 초기화

        for j in range(W):
            tmpcnt = []
            for i in range(H-1,-1,-1):
                if acc[i][j] != 0: # 8. acc의 배열의 y축을 우선 돌며 값이 있다면 tmpcnt에 추가 
                    tmpcnt.append(acc[i][j])
            for i in range(H-1,-1,-1):
                if tmpcnt == []:
                    break
                drop[i][j] = tmpcnt.pop(0) # 9. drop 임시배열에 아래서부터 쌓아줌

        acc = copy.deepcopy(drop) # 10. 배열을 새로 쌓은 후 drop을 acc에 깊은 복사를해줌

    def crush(x): 3. 해당하는 y축에 벽돌이 있다면 bfs실행
        global used

        for j in range(H):
            if acc[j][x] != 0:
                bfs(j,x)
                break


    for j in range(len(combo)):
        acc = copy.deepcopy(arr) # 2. acc 임시 배열을 계속 원상태로 복구시킴
        for i in range(len(combo[j])):
            crush(combo[j][i]) # 3. 구한 순열로 crush 함수 호출 
        cnt = 0
        for jj in range(H):
            for ii in range(W):
                if acc[jj][ii] != 0:
                    cnt += 1 # 11. 순열을 한번 돌 때마다 벽돌의 수 확인
        result.append(cnt)

    print(f'#{tc} {min(result)}') # 12. 결과 값중 가장 작은 벽돌의 수를 출력