[Python] SW Expert Academy #5656 벽돌 깨기

📚문제: #5656 벽돌 깨기(모의 SW 역량테스트)

전체 코드

# 5656 벽돌 깨기

from collections import deque
from copy import deepcopy

# 벽돌 깨기 함수(백트래킹)
def Break(n, G):
    
    # 전역변수 선언
    global min_remain_bricks
    
    # 상하좌우
    dr = [-1, 1, 0, 0]
    dc = [0, 0, -1, 1]
    
    # 종료 조건
    if n == N:
        
        # 남은 벽돌 개수를 셉니다.
        remain = 0
        
        for i in range(H):
            
            for j in range(W):
                
                if G[i][j] > 0:
                    
                    remain += 1
        
        # 갱신
        min_remain_bricks = min(min_remain_bricks, remain)
        return
    
    # 벽돌이 없을 때
    remain = 0
    for i in range(H):
        
        for j in range(W):
            
            if G[i][j] > 0:
                
                remain += 1
    
    if remain == 0:
        
        min_remain_bricks = 0
        return
    
    # N번 구슬을 쏜다.
    
    # 떨어질 위치
    for loc in range(W):

        copied = deepcopy(G)
        
        # 해당 열에 벽돌이 존재하는지
        brick_exist = False
        
        # 구슬이 처음으로 부딪히게 될 위치를 찾는다.
        for r in range(H):
            
            if copied[r][loc] > 0:
                
                brick_exist = True
                init = [r, loc]
                break
        
        # 해당 열에 벽돌이 존재하지 않을 때
        if not brick_exist:
            
            Break(n+1, copied)
            continue
        
        # 큐 선언
        q = deque()
        
        # 부딪히는 위치
        init_r, init_c = init
        
        # 처음 시작 (좌표, 벽돌 값)
        s = (init, copied[init_r][init_c])
        
        q.append(s)
        
        # 구슬을 떨어트리고 벽돌을 깬다.
        while q:
            
            # 큐에서 꺼낸다.
            coord, val= q.popleft()
            
            # 좌표
            cur_r, cur_c = coord
            
            # 꺼냈는데 이미 깨진 벽돌이면 skip, 실행시간 단축
            if copied[cur_r][cur_c] == 0:
                
                continue
            
            # 벽돌 값이 1일 때는 하나만 깨고 skip, 큐에 추가 안함
            if val == 1:
                
                copied[cur_r][cur_c] = 0
            
            # 벽돌 값이 1보다 클 때, 추가로 깨진다.
            elif val > 1:
                
                # 현재 벽돌이 깨진다.
                copied[cur_r][cur_c] = 0
                
                # 상하좌우 칸들을 큐에 포함시킨다.
                for i in range(4):
                    
                    for m in range(1, val):
                        
                        move_r, move_c = cur_r + dr[i] * m, cur_c + dc[i] * m
                        
                        # 주어진 범위를 벗어나지 않을 때
                        if 0 <= move_r <= H-1 and 0 <= move_c <= W-1:
                            
                            # 벽돌이 있을 때만 큐에 추가
                            if copied[move_r][move_c] > 0:
                                
                                p = ([move_r, move_c], copied[move_r][move_c])
                                q.append(p)
        
        # 벽돌 재정렬
        for i in range(W):
            
            col_temp = []
            
            for j in range(H-1, -1, -1):
                
                if copied[j][i] > 0:
                    
                    col_temp.append(copied[j][i])
                
            for _ in range(H-len(col_temp)):
                
                col_temp.append(0)
            
            # 역순
            col_temp = col_temp[::-1]
            
            for m in range(H):
                
                copied[m][i] = col_temp[m]
        
        # 재귀 호출
        Break(n+1, copied)
                  
# 총 테스트 케이스의 개수 T
T = int(input())

# T 개의 테스트 케이스가 주어진다.
for t in range(1, T+1):
    
    # 남은 벽돌 최소 개수
    min_remain_bricks = int(1e10)
    
    # N, W, H가 순서대로 주어진다.
    N, W, H = map(int, input().split())
    
    # 벽돌 초기화
    bricks = []
    
    # H줄에 걸쳐 벽돌들의 정보가 주어진다.
    for _ in range(H):
        
        bricks.append(list(map(int, input().split())))
    
    # 함수 실행
    Break(0, bricks)
    
    # 답안 출력
    print("#{} {}".format(t, min_remain_bricks))

TIL

중복순열 개념을 백트래킹으로 구현하는 문제다. 구슬을 떨어트리는 열에 벽돌이 있는지 없는지, 구슬을 떨어트리는 시점에 게임판에 벽돌이 존재하는지 등 예외처리를 해주어야할 경우가 많다.