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

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

SW Expert Academy

1. 문제 설명

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

구슬은 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 부터 시작한다)

 

2. 코드

코드를 짜기 조금 힘들었습니다. 연쇄적으로 생각해줘야 할 것도 많고 해서 다른 사람의 코드를 참고해서 풀게 되었습니다. 풀고 보니 dfs, bfs 등 제가 아는 모든 방법이 들어간 것 같아보였습니다...

제가 생각했던 로직과는 같아서 이해하는 것은 괜찮았는데 코드를 직접 짜는건 조금 오래 걸렸습니다. 마지막에 인덱스 하나가 차이가 난 문제를 찾는데 두시간정도 걸린건 비밀...

제대로 공부할 수 있던 문제인거 같습니다.

 

아래가 작성한 코드입니다.

# 인덱스 범위를 제한해주기 위한 함수
def boundary(x, y):
    if x < 0 or y < 0 or x > W-1 or y > H-1:
        return False
    return True
 
# 벽돌에 구슬이 맞았을 때 벽돌을 제거하기 위한 함수
def remove(c, copy_arr):
    q = []
    r = 0
    # 구슬을 쏜 colum에서 첫번째로 있는 벽돌을 검사
    while boundary(c, r) and copy_arr[r][c] == 0:
        r += 1
    # 구슬을 쏜 colum에서 첫번째로 있는 벽돌이 없으면 종료
    if r == H:
        return
    # 해당 벽돌 위치를, q에 추가
    q.append([c, r])
    # 연쇄 적으로 없어지는 벽돌을 없애기 위한 반복문
    while len(q):
        x, y = q.pop(0)
        # 벽돌에 적힌 숫자를 저장하고 0으로 변경
        k = copy_arr[y][x]
        copy_arr[y][x] = 0
        # 4방향 진행
        for d in range(4):
            # 벽돌에 적힌 숫자-1 까지 진행
            for n in range(1, k):
                if boundary(x+n*dx[d],y+n*dy[d]):
                    # 인덱스 내부일 경우 q에 추가하여 다시 진행
                    q.append([x+n*dx[d],y+n*dy[d]])
 
# 구슬을 쏘고 정렬하기 위한 함수
def shot():
    # 배열을 copy (구슬을 새로 쏠 때마다)
    copy_arr = [[0]*W for _ in range(H)]
    for j in range(H):
        for i in range(W):
            copy_arr[j][i] = arr[j][i]
    # 구슬 개수만큼 진행
    for k in range(N):
        remove(p[k], copy_arr)
        # 구슬 하나를 쏘고 나서 벽돌을 밑으로 정렬
        for x in range(W):
            for y in range(H-1, 0, -1):
                temp = y
                while(temp >= 1 and copy_arr[temp][x] == 0):
                    temp -=1
                if temp != y:
                    copy_arr[y][x] = copy_arr[temp][x]
                    copy_arr[temp][x] = 0
    # 남아 있는 벽돌 개수 체크
    cnt = 0
    for j in range(H):
        for i in range(W):
            if copy_arr[j][i]:
                cnt += 1
    return cnt
 
# 구슬을 쏘는 위치를 정하는 함수
def npr(n):
    global count
    # 구슬을 쏘는 위치를 모두 정하였을 때 실행
    if n == N:
        result = shot()
        if result < count:
            count = result
    else:
        # 구슬을 쏘는 위치를 중복순열로 생성
        for i in range(W):
            p[n] = i
            npr(n+1)
            if count == 0:
                return
 
T = int(input())
for t in range(1, T+1):
    N, W, H = map(int, input().split())
    arr = [list(map(int,input().split())) for _ in range(H)]
    # 우, 좌, 하, 상
    dx = [1, -1, 0, 0]
    dy = [0, 0, 1, -1]
    p = [0] * N
    # 벽돌개수의 최고값 부여
    count = H*W
    npr(0)
    print('#{} {}'.format(t, count))