[모의 SW 역량테스트][Python] 벽돌 깨기

벽돌 깨기

SW Expert Academy

 

<문제 풀이 Logic>

crash(): 구슬이 벽돌이 깨뜨릴 때 호출되는 함수. 벽돌이 또 다른 벽돌을 깰 때도 호출됨

removeEmpty(): 벽돌이 다 깨진 후 사이사이의 빈공간을 없애주는 함수

 

-> 백트래킹으로 구현했음

1. possible 리스트에는 각 열에서 처음으로 깨질 행의 번호가 저장되어 있다.

2. 구슬을 쏠 수 있는 범위(0~W-1)만큼 crash -> removeEmpty를 한다. 다시 재귀로 호출

3. arr와 possibe 다시 원상태로 돌리기

4. 구슬을 쏠 수 있는 횟수만큼 다 쏘거나 그 전에 모든 벽돌이 깨진다면 solution() 종료

 

 

-전체 코드-

import sys
import copy

pos = [[1,0],[-1,0],[0,1],[0,-1]]
N = 0
W = 0
H = 0
possible = []
answer = []

def isIn(x, y):
    if (x>=0 and x<W and y >=0 and y<H):
        return True
    return False

def crash(x, y, cnt, arr):
    arr[y][x] = 0
    for c in range(1, cnt):
        for i in range(0, 4):
            nx = x + pos[i][1]*c
            ny = y + pos[i][0]*c
            if(isIn(nx, ny) and arr[ny][nx] > 0):
                crash(nx, ny, arr[ny][nx], arr)

def removeEmpty(arr, possible):
    for i in range(0, W):
        tmp = [0 for x in range(H)]
        idx = H-1
        for j in range(H-1, -1, -1):
            if(arr[j][i] != 0):
                tmp[idx] = arr[j][i]
                arr[j][i]= 0
                idx -= 1
        for j in range(H):
            arr[j][i] = tmp[j]
        
        flag = 0
        for j in range(H):
            if(tmp[j] != 0):
                flag = 1
                possible[i] = j
                break
        if(flag == 0):
            possible[i] = H
        


def solution(now_c, goal_c, arr, possible):
    cnt = 0
    for i in range(H):
        cnt += arr[i].count(0)

    if(cnt == W*H):
        answer.append(0)
        return
    
    if(now_c == goal_c):
        cnt = 0
        for i in range(0, H):
            cnt += arr[i].count(0)
        answer.append(W*H - cnt)

        return
        
    for i in range(0, W):
        j = possible[i]
        if(j < H and arr[j][i] != 0):
            tmp_arr = copy.deepcopy(arr)
            tmp_possible = copy.deepcopy(possible)
            crash(i, j, arr[j][i], arr)
            removeEmpty(arr, possible)
            solution(now_c+1, goal_c, arr, possible)
            arr = copy.deepcopy(tmp_arr)
            possible = copy.deepcopy(tmp_possible)



T = int(input())
# 여러개의 테스트 케이스가 주어지므로, 각각을 처리합니다.
for test_case in range(1, T + 1):
    answer = []
    N, W, H = map(int, input().split())
    arr = [[int(x) for x in input().split()]for y in range(H)]
    possible = [0 for x in range(W)]

    for i in range(W):
        for j in range(H):
            if(arr[j][i] > 0): 
                possible[i] = j
                break
        
    solution(0, N, arr, possible)
    print("#" + str(test_case) + " " + str(min(answer)))