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

※ 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 부터 시작한다)

 

 

 

 

#include <iostream>
#include <queue>
 
using namespace std;
 
int n,w,h, MAP[16][13], temp[16][13], ans = 0;
int mx[] = {0,1,0,-1}, my[] = {1,0,-1,0};
 
queue<pair<int, int> >q;
queue<int> fall;
 
void boom(int arr[][13],int idx) //벽돌 부시기
{
    for(int i=0;i<h;i++)   //구슬이 처음 떨어진 곳 찾기
        if(arr[i][idx] != 0)
        {
            q.push({i,idx});
            break;
        }
 
 
    while(!q.empty())  //연쇄 작용
    {
        int x = q.front().first;
        int y = q.front().second;
        int power = arr[x][y];
        q.pop();
        arr[x][y] = 0;
 
        for(int i=1;i<power;i++)
            for(int j=0;j<4;j++)
            {
                int nx = x + mx[j] * i;
                int ny = y + my[j] * i;
 
                if(nx<0||ny<0||nx>=h||ny>=w) continue;
 
                if(arr[nx][ny] > 1)
                    q.push({nx,ny});
                else
                    arr[nx][ny] = 0;
            }
    }
 
    for(int i= 0;i<w;i++)   // 벽돌 내려가기
    {
        for(int j=h-1;j>=0;j--)
        {
            if(arr[j][i] != 0)
            {
                fall.push(arr[j][i]);
                arr[j][i] = 0;
            }
        }
        int idx = h - 1;
        while(!fall.empty())
        {
            arr[idx][i] = fall.front();
            fall.pop();
            idx--;
        }
 
    }
    for(int i=0;i<h;i++) //다음 연산을 위해 행렬 복사
        for(int j=0;j<w;j++)
            temp[i][j] = arr[i][j];
 
    return;
}
void solve(int cnt, int arr[][13])
{
    if(cnt == 0) //구슬을 모두 떨어뜨렸을 때, 남은 벽돌 개수 조사
    {
        int block = 0;
        for(int i=0;i<h;i++)
            for(int j=0;j<w;j++)
                if(arr[i][j] > 0) block++;
        if(block < ans)
            ans = block;
        return;
    }
 
    int before[16][13]; //이전 행렬 기억하기
    for(int i=0;i<w;i++)
    {
        for(int i=0;i<h;i++)
            for(int j=0;j<w;j++)
                before[i][j] = arr[i][j];
                
        boom(arr,i);
        solve(cnt - 1, temp);
        
        for(int i=0;i<h;i++)
            for(int j=0;j<w;j++)
                arr[i][j] = before[i][j] ;
    }
 
}
int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    int tc;
    cin>>tc;
 
    for(int t=1;t<=tc;t++) 
    {
        ans = 99999999;
        cin>>n>>w>>h;
        for(int i=0;i<h;i++)
            for(int j=0;j<w;j++)
                cin>>MAP[i][j];
 
        solve(n, MAP);
        cout<<'#'<<t<<' '<<ans<<'\n';
    }
    return 0;
}
 

 

처음에 구슬이 떨어지는 곳을 찾고 한꺼번에 떨어뜨리는 방법으로 했더니 시간 초과가 났다.

그래서 구슬이 떨어질 때마다 행렬을 기억해 이어나가는 방법으로 풀었다.

 

처음에 행렬을 입력 받고 구슬을 떨어뜨릴 곳을 DFS로 탐색한다.

이전 행렬을 기억한 배열을 하나 만들어 놓고 DFS가 끝나면 다시 원래 배열로 바꿔준다. <- 이게 핵심

떨어 뜨리는 것은 큐를 이용하는데 처음 구슬이 벽돌과 만나는 지점만 큐에 넣는다.

이후 연쇄작용을 일으켜 깰 수 있는 모든 벽돌을 깬다.

 

큐가 다 끝난 후에

빈 공간이 있으면 벽돌이 아래로 떨어뜨린다.

 

모든 구슬을 다 썼으면 남은 벽돌의 개수를 샌다.