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

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

문제 내용

• 시간 : 50개 테스트케이스를 합쳐서 C의 경우 3초 / C++의 경우 3초 / Java의 경우 3초 / Python의 경우 15초
• 메모리 : 힙, 정적 메모리 합쳐서 256MB 이내, 스택 메모리 1MB 이내

※ SW Expert 아카데미의 문제를 무단 복제하는 것을 금지합니다. 


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

구슬은 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

// T = 5 // #1, N = 3, W = 10, H = 10 // #2, N = 2, W = 9, H = 10 // 이하 sample_input.txt 참조

sample_input.txt

출력

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

sample_output.txt

=====================================================================================

[IDEA]

: 우선 DFS로 벽돌을 떨어뜨릴 열의 위치를 일차원 배열에 저장했다. (make(int cnted))

  그 다음 DFS로 벽돌을 순서대로 깨도록 했다 (Crash(int x,int y))

  이 문제에서 가장 중요했던건 벽돌을 깬 후, 빈 부분 없이 다시 밑에서부터 채우는 것이 중요했던 문제라고 생각한다.

  queue로 밑에서부터 탐색해서 0이 아닌 값을 가진 곳을 queue에 집어넣고 0으로 만들었다. 

  이후 queue가 빌때까지 밑에서부터 채워나갔다(당연히 pop해준다) (reset())

==> 그러고 나서, 남아있는 벽돌의 개수를 세어주고 (Calculate()), 다시 원배열로 돌려줬다(Clear())

 

[Codes]

벽돌 깨기.txt