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

1. 구슬이 떨어지는 모든 조합을 구한다. 

ex) W는 10, N은 3이면 0,0,0 ~10, 10, 10까지.

2. 조합을 구한 후, Q에 넣으면서 구슬을 떨어뜨린다.

3. 떨어뜨리면서 터지는 빈칸들을 Q에 넣고, 계속 터트린다.

4. 다 터트린 후, MAP을 아래로 내린다.

나는 1000msec 정도 나왔는데...어떻게하면 50msec이하가 나오지...??ㅜ,ㅠ

이건 다른사람 코드도 못 봐서ㅜㅠ

#include <stdio.h>
#include <string.h>
 
typedef struct
{
    int y, x, len;
}point;
 
int map[20][20];
int Down[5], N, H, W, MIN, Q_Front, Q_Back;
point Q[17 * 17];
 
void DFS(int cur, int n)
{
    if (n == N)
    {
 
        int copy[20][20];
        int count = 0;
        for (int i = 0; i <= H + 1; i++)
            for (int j = 0; j <= W + 1; j++)
                copy[i][j] = map[i][j];
 
        Q_Front = -1;
        Q_Back = -1;
        memset(Q, 0, sizeof(Q));
 
        for (int i = 0; i < N; i++)
        {
            int W_position = Down[i];
            int H_position = 0;
 
            for (int j = 1; j <= H; j++)
            {
                if (copy[j][W_position] != 0)
                {
                    H_position = j; break;
                }
            }
 
            Q[++Q_Back].y = H_position;
            Q[Q_Back].x = W_position;
            Q[Q_Back].len = copy[H_position][W_position];
 
 
            while (Q_Front != Q_Back)
            {
                int y = Q[++Q_Front].y;
                int x = Q[Q_Front].x;
                int len = Q[Q_Front].len;
 
                for (int a = 1; a < len; a++)
                {
                    //상
                    if (y - a > 0 && copy[y - a][x] > 0)
                    {
                        Q[++Q_Back].y = y - a;
                        Q[Q_Back].x = x;
                        Q[Q_Back].len = copy[y - a][x];
                        copy[y - a][x] = 0;
                    }
 
                    //하
                    if (y + a <= H && copy[y + a][x] > 0)
                    {
                        Q[++Q_Back].y = y + a;
                        Q[Q_Back].x = x;
                        Q[Q_Back].len = copy[y + a][x];
                        copy[y + a][x] = 0;
                    }
 
                    //우
                    if (x + a <= W && copy[y][x + a] > 0)
                    {
                        Q[++Q_Back].y = y;
                        Q[Q_Back].x = x + a;
                        Q[Q_Back].len = copy[y][x + a];
                        copy[y][x + a] = 0;
                    }
 
                    //좌
                    if (x - a > 0 && copy[y][x - a] > 0)
                    {
                        Q[++Q_Back].y = y;
                        Q[Q_Back].x = x - a;
                        Q[Q_Back].len = copy[y][x - a];
                        copy[y][x - a] = 0;
                    }
                }
 
                copy[y][x] = 0;
            }
 
            for (int a = 1; a <= W; a++)
            {
                for (int b = H; b > 0; b--)
                {
                    if (copy[b][a] == 0)
                    {
                        for (int c = b - 1; c > 0; c--)
                        {
                            if (copy[c][a] > 0)
                            {
                                copy[b][a] = copy[c][a];
                                copy[c][a] = 0;
                                break;
                            }
                        }
                    }
                }
            }
        }
 
        for (int i = 1; i <= H; i++)
        {
            for (int j = 1; j <= W; j++)
            {
                if (copy[i][j] != 0)
                    count++;
            }
        }
 
        if (MIN > count)
            MIN = count;
 
        return;
    }
 
    for (int i = cur + 1; i < N; i++)
    {
        for (int j = 1; j <= W; j++)
        {
            Down[i] = j;
            DFS(i, n + 1);
            Down[i] = 0;
        }
    }
    return;
}
 
int main()
{
    int Test_Case;
    scanf("%d",&Test_Case);
 
    for (int T = 1; T <= Test_Case; T++)
    {
        Q_Front = -1;
        Q_Back = -1;
        memset(Q, 0, sizeof(Q));
        MIN = 987654321;
        memset(map, -1, sizeof(map));
 
        scanf("%d %d %d", &N, &W, &H);
 
        for(int i = 1 ; i <= H ; i++)
        {
            for (int j = 1; j <= W; j++)
            {
                scanf("%d", &map[i][j]);
            }
        }
 
        DFS(-1, 0);
 
        printf("#%d %d\n", T, MIN);
    }
 
    return 0;
}