[SWEA] 5656. 벽돌 깨기 (Python)

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

SW Expert Academy

 

1️⃣ DFS로 칠 벽돌 고르기

2️⃣ BFS로 벽돌에 쓰여 있는 만큼 상하좌우 제거

3️⃣ gravity() 함수로 벽돌 내려주기, for문 사용

 

from collections import deque
import copy
 
# 중력에 따라 벽돌 내려주기
def gravity():
    for j in range(W):
        for i in range(H-1, 0, -1): # H-1 ~ 1까지 거꾸로 탐색
            if board[i][j] == 0: # 0을 만나면
                for k in range(i-1, -1, -1): # 윗쪽으로 탐색
                    if board[k][j] != 0: # 0이 아닌 수를 만나면 스왑
                        board[i][j], board[k][j] = board[k][j], board[i][j] 
                        break
 
# 벽돌 제거
def bomb(y, x):
    q = deque()
    q.append((y, x, board[y][x]))
    while q:
        nowy, nowx, n = q.popleft()
        board[nowy][nowx] = 0 # 폭탄 터지는 자리 벽돌 제거
        directy = [-1, 1, 0, 0]
        directx = [0, 0, -1, 1]
        for i in range(n): # 벽돌에 적힌 숫자 -1만큼
            for j in range(4):
                dy = directy[j]*i+nowy # 범위 지정
                dx = directx[j]*i+nowx
                if 0 <= dy < H and 0 <= dx < W:
                    if board[dy][dx] != 0: # 벽돌이 있으면
                        q.append((dy, dx, board[dy][dx])) # q에 추가하여 없애주기
    gravity()
 
# 남은 벽돌 수 세기
def check():
    cnt = 0
    for i in range(H):
        for j in range(W):
            if board[i][j] != 0:
                cnt += 1
    return cnt
 
# dfs
def dfs(level):
    global board, Min
    if level == N:
        ret = check()
        if Min > ret:
            Min = ret
        return
    backup = copy.deepcopy(board)
    flag = 1
    for j in range(W):
        for i in range(H):
            if board[i][j] != 0:
                flag = 0
                bomb(i, j)
                dfs(level+1)
                board = copy.deepcopy(backup)
                break
                 
    # Level N 전에 배열 안에 벽돌이 하나도 없으면
    if flag:
        Min = 0 # 0 리턴
        return
 
 
t = int(input())
 
for tc in range(1, t+1):
    N, W, H = map(int, input().split())
    board = [list(map(int, input().split())) for _ in range(H)]
    Min = 2e18
    dfs(0)
    print(f'#{tc} {Min}')

💥주의

• W, H 잘 구분! 둘 바꿔쓴지도 모르고 한참을 디버깅...🙃
• 범위 지정 잘 해주기... 언제나 제일 헷갈리는 인덱스 범위 지정해주기...🥲