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

문제 출처

https://swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AWXRQm6qfL0DFAUo&categoryId=AWXRQm6qfL0DFAUo&categoryType=CODE

문제

구술을 쏘아 벽돌을 깨트리는 게임을 하려고 한다.

구슬은 N번만 쏠 수 있고, 벽돌들의 정보는 아래와 같이 W x H 배열로 주어진다.

( 0 은 빈 공간을 의미하며, 그 외의 숫자는 벽돌을 의미한다. )

 

게임의 규칙은 다음과 같다.

① 구슬은 좌, 우로만 움직일 수 있어서 항상 맨 위에 있는 벽돌만 깨트릴 수 있다.

② 벽돌은 숫자 1 ~ 9 로 표현되며,

   구술이 명중한 벽돌은 상하좌우로 ( 벽돌에 적힌 숫자 - 1 ) 칸 만큼 같이 제거된다.

 

아래는 벽돌에 적힌 숫자와, 구술이 명중했을 시 제거되는 범위의 예이다.

 

③ 제거되는 범위 내에 있는 벽돌은 동시에 제거된다.

 

예를 들어 아래와 같이 4 번 벽돌에 구술이 명중할 경우,

 

 

9번 벽돌은 4 번 벽돌에 반응하여,

 

 

동시에 제거된다.

 

 

④ 빈 공간이 있을 경우 벽돌은 밑으로 떨어지게 된다.

 

 

N 개의 벽돌을 떨어트려 최대한 많은 벽돌을 제거하려고 한다.

N, W, H, 그리고 벽돌들의 정보가 주어질 때,

▶ 남은 벽돌의 개수를 구하라!

 

※ sample input 1

 

N = 3, W = 10, K = 10 이고 벽돌들의 정보가 아래와 같을 때,

 

 

최대한 많은 벽돌을 깨트리는 방법은 아래와 같으며, 정답은 12 가 된다.

그림의 빨간 색 원은 구술이 명중한 위치이며, 주황색 칸은 폭발의 범위를 의미한다.

 

 

i) 첫 번째 구술

 

 

ii) 두 번째 구술

 

 

iii) 세 번째 구술

 

 

[제약 사항]

1. 1 ≤ N ≤ 4

2. 2 ≤ W ≤ 12

3. 2 ≤ H ≤ 15

 

[입력]

가장 첫 줄에는 총 테스트 케이스의 개수 T 가 주어지고,

그 다음 줄부터 T 개의 테스트 케이스가 주어진다.

각 테스트 케이스의 첫 번째 줄에는 N, W, H 가 순서대로 공백을 사이에 두고 주어지고,

다음 H 줄에 걸쳐 벽돌들의 정보가 1 줄에 W 개씩 주어진다.

 

[출력]

출력은 #t 를 찍고 한 칸 띄운 다음 정답을 출력한다.

(t 는 테스트 케이스의 번호를 의미하며 1 부터 시작한다)

5 3 10 10 0 0 0 0 0 0 0 0 0 0 1 0 1 0 1 0 0 0 0 0 1 0 3 0 1 1 0 0 0 1 1 1 1 0 1 2 0 0 0 9 1 1 4 0 1 1 0 0 1 1 1 1 4 1 1 1 2 1 1 1 1 1 5 1 1 1 1 2 1 1 1 1 6 1 1 1 1 1 2 1 1 1 1 1 1 1 1 1 1 5 1 1 7 1 1 1 1 1 1 1 2 9 10 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 1 1 0 0 1 0 0 0 0 1 1 0 1 1 1 0 1 0 1 1 0 1 1 1 0 1 0 1 1 1 1 1 1 1 1 0 1 1 3 1 6 1 1 1 1 1 1 1 1 1 1 1 1 1

#1 12 #2 27 #3 4 #4 8 #5 0

 

풀이

DFS 와 BFS를 함께 사용했다. 구슬을 쏘는 위치를 탐색함에 있어 DFS를 활용해 탐색을 하였고 구슬을 쏘는 위치(행,열)을 구하게 되면 그 자리에서부터 연쇄 폭발을 하게 되는 부분을 BFS를 활용함으로서 해결하였다. 

유의할점은 DFS후 다시 백트래킹 할 때이다. 이미 게임판은 연쇄폭발로 부숴진 상태이기에 폭발이 일어나기 전의 게임판으로 복구를 해줘야한다. 그러므로 BFS로 연쇄폭발을 하기 전에 미리 현재 상태의 게임판을 복사를 해 놓고 백트래킹 후에 그 복사된 게임판으로 복구를 하면 된다.

 

코드

import copy
def dfs(idx,mapp2):
    global block_cnt
    if idx == N: # 종료 기준 = 슛팅횟수만큼 탐색
        cnt = 0
        for z in range(H): # 0을 세서 전체 리스트 요소 개수에서 빼주면 남은 벽돌 개수가 나옴
            cnt += mapp2[z].count(0)
        result_cnt = W*H - cnt
        if result_cnt < block_cnt:
            block_cnt = result_cnt
        return
 
    for y in range(W): # 구슬 쏘는 위치(열)
        check = 0
        for x in range(H): # 가장 위에 있는 벽돌을 찾음 (행)
            if not mapp2[x][y]: # 맵이 0이면 블록이 없다는 뜻이기에 다음 행 탐색
                continue
            else: 
                init_mapp = copy.deepcopy(mapp2) # 초기맵 복사 // 맵을 터뜨릴꺼기에 백트래킹 때 맵 복구를 위해서
                q = [(x,y,mapp2[x][y])] 
                while q: # BFS // 가능한 벽돌 다 터뜨림
                    qq = q.pop(0)
                    if qq[2] == 1: #블록숫자가 1이면 자기만 터짐
                        mapp2[qq[0]][qq[1]] = 0
                    else:
                        mapp2[qq[0]][qq[1]] = 0 
                        for k in range(1,qq[2]): # 블록 숫자 - 1만큼 연쇄폭발
                            for i in range(4):
                                if 0 <= qq[0]+dx[i]*k < H and 0 <= qq[1]+dy[i]*k < W and mapp2[qq[0]+dx[i]*k][qq[1]+dy[i]*k] != 0:
                                    if (qq[0]+dx[i]*k,qq[1]+dy[i]*k,mapp2[qq[0]+dx[i]*k][qq[1]+dy[i]*k]) not in q: # 큐에 중복으로 들어가는 것 방지                  
                                        q.append((qq[0]+dx[i]*k,qq[1]+dy[i]*k,mapp2[qq[0]+dx[i]*k][qq[1]+dy[i]*k]))
            
                mapp3 = [[0 for _ in range(W)] for _ in range(H)]
                for j in range(W): # 벽돌 아래로 내리는 작업
                    temp = []
                    for i in range(H):
                        if mapp2[i][j]:
                            temp.append(mapp2[i][j])   
                    for a in range(len(temp)):
                        mapp3[H-len(temp)+a][j] = temp[a]
                check = 1 # 선택된 열에서 가장 높은 위치의 벽돌을 찾는 것이기에 행을 찾게 되면 그 다음 행을 탐색하면 안되기에 check를 통해 방지
            if check == 1: 
                dfs(idx+1,mapp3)
                mapp2 = init_mapp
                break
    dfs(N,mapp2) # 모든 행 열을 탐색해도 벽돌이 없다면 종료시킬 것임
 
T = int(input())
for t in range(T):
    N, W, H = map(int,input().split()) 
    mapp =[list(map(int,input().split())) for _ in range(H)]
    block_cnt = 999999999
    dx = [1,-1,0,0]
    dy = [0,0,1,-1]
    dfs(0,mapp) 
    print('#{} {}'.format(t+1,block_cnt))