[SW Expert Academy / 5658] 벽돌 깨기

1. 문제이해

입력값:
 N : 구슬 쏠 수 있는 횟수  
 W : 벽돌 맵 가로
 H : 벽돌 맵 세로
 
유의해야 할 점:
 벽돌을 깨면 4방향으로 그 벽돌의 수-1 만큼 벽돌을 깨게 된다.

출력값:
최대한 많은 벽돌을 깨트리고 남은 벽돌의 수

 

2. 문제 풀이 법

사용한 방법:
 1. comb() 함수로 중복 조합을 사용하여 어떤 열의 벽돌을 깨 트릴지 순서를 정한다.
 2. play() 함수로 bfs와같이 queue를 이용하여 깬다.
 3. zero() 함수로 벽돌들을 아래로 내려준다. 

 

3. 어려웠던 점

1. 문제 이해를 아예 못했었다.
2. 어떻게 벽돌을 다시 내릴지에대해서 잘 몰랐었다.

< 앞으로 고쳐야 할 점 >
1. zero 함수에서 시간을 좀 더 줄일 방법이 있을 것이다 

import sys
import copy
sys.stdin = open('5656.txt')


T = int(input())

def zero(box2):
    flag = 0
    while flag ==0 :
        flag = 1
        for a in range(H-1,-1,-1):# 행
            for b in range(W): #열
                if box2[a][b] == 0 and box2[a-1][b] != 0:
                    if a-1 >= 0:
                        box2[a][b], box2[a-1][b] =  box2[a-1][b], 0
                        flag = 0



def play(c, r, box2) : # 열 행
    q = [[c, r, box2[r][c]]]
    temp_cnt = 0

    while q:
        x, y, s = q.pop() # 열, 행, 값
        for k in range(4): #4방향 탐색
            for ss in range(s):
                temp_x = x + ss * dx[k]
                temp_y = y + ss * dy[k]
                
                if 0 <= temp_x < W and 0 <= temp_y < H:
                    if box2[temp_y][temp_x] != 0:
                        q.append([temp_x, temp_y, box2[temp_y][temp_x]])
                        box2[temp_y][temp_x] = 0
                        temp_cnt += 1

    zero(box2)
    return temp_cnt

def comb(n):
    global ans
    if ans == total:
        return
        
    if n == N:
        box2 = copy.deepcopy(box)
        cnt = 0

        for i in ball:# 공 던지는 순서, 열
            r = -1
            for j in range(H): # 행
                if box2[j][i] != 0:
                    r = 0
                    l = j
                    break

            if r == -1: # 벽돌이 없을 때
                if cnt >= ans:
                    ans = cnt
                return

            cnt +=  play(i,l,box2) # 열, 행

        if cnt > ans:
            ans = cnt       
    else:
        for i in range(W):
            ball[n] = bal[i]
            comb(n+1)
        

for tc in range(1, T+1):
    N, W, H = map(int,input().split())
    box = [list(map(int,input().split())) for _ in range(H)]
    bal = [ _ for _ in range(W) ] # 공이 던져질 수 있는
    ball = [0 for _ in range(N)] # N회의 공 던지는 순서를 담을 배열
    total = 0
    ans = 0

    for i in range(W): # 초기 벽돌 수 
        for j in range(H):
            if box[j][i] != 0:
                total += 1

    dx = [1, 0, -1, 0] # 오른쪽부터 시계방향
    dy = [0, 1, 0, -1]
    comb(0)
    print('#{} {}'.format(tc,total - ans))

 

4. 배운 점

import copy
copy.deepcopy(배열) 하면 깊은 복사를 할 수 있다.

 

 

혹시 더 좋은 풀이나 조언이 있다면 댓글 달아주시거나 

nsk324@naver.com으로 메일 보내주십시오!