[SWEA] 5656 - 벽돌 깨기

https://www.swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AWXRQm6qfL0DFAUo

(이 글이 문제가 될 시 삭제하도록 하겠습니다.)

시뮬레이션 카테고리로 올려두긴 했지만 DFS + BFS로 풀었다

먼저 구슬을 쏘는 순서를 DFS로 정해 준 뒤, BFS로 연쇄적으로 삭제한 아래로 내리는 순서로 해결했다

하지만 시간효율은 썩 좋지 않은 1.8s가 나옴

다른 사람들은 더 짧은 시간이 걸리는데 아마 내 코드 중에 맵을 카피하는 과정에서 시간을 많이 잡아먹은 듯 하다

#include <iostream>
#include <cstdio>
#define MX 20
#define INF 987654321
using namespace std;
 
struct BREAK {
    int x, y;
}q[MX*MX*MX];
 
int map[MX][MX], arr[6], check[MX][MX];
int dx[] = { 0, 0, -1, 1 };
int dy[] = { -1, 1, 0, 0 };
int T, N, W, H, dab;
 
void bfs(int x, int y)
{
    int st, ed, ix, iy, nx, ny;
    st = ed = -1;
    q[++st].x = x; q[st].y = y;
    while (st != ed)
    {
        ix = q[++ed].x; iy = q[ed].y;
        for (int i = 0; i < 4; i++)
        {
            for (int j = 0; j < check[iy][ix]; j++)
            {
                nx = ix + j * dx[i]; ny = iy + j * dy[i];
                if (nx < 0 || ny < 0 || nx >= W || ny >= H) break;
                if (!check[ny][nx]) continue;
                q[++st].x = nx; q[st].y = ny;
            }
        }
        check[iy][ix] = 0;
    }
}
 
void gravity()
{
    for (int j = 0; j < W; j++)
        for (int i = H - 1; i >= 0; i--)
            if (check[i][j])
            {
                int x, y;
                x = j; y = i;
                while (1)
                {
                    if (check[y + 1][x] || y + 1 >= H) break;
                    check[y + 1][x] = check[y][x];
                    check[y][x] = 0;
                    y++;
                }
            }
}
void mapcopy()
{
    for (int i = 0; i < H; i++)
        for (int j = 0; j < W; j++)
            check[i][j] = map[i][j];
}
void boom()
{
    int ret = 0;
    mapcopy();
    for (int pos = 0; pos < N; pos++)
    {
        int x = arr[pos];
        for (int y = 0; y < H; y++)
        {
            if (check[y][x]) { bfs(x, y); gravity(); break; }
        }
    }
    for (int i = 0; i < H; i++)
        for (int j = 0; j < W; j++)
            if (check[i][j]) ret++;
    dab = dab > ret ? ret : dab;
}
 
void dfs(int d)
{
    if (d == N)
    {
        boom();
        return;
    }
 
    for (int i = 0; i < W; i++)
    {
        arr[d] = i;
        dfs(d + 1);
    }
}
 
int main(void)
{
    scanf("%d", &T);
    for (int tc = 1; tc <= T; tc++)
    {
        dab = INF;
        scanf("%d %d %d", &N, &W, &H);
        for (int i = 0; i < H; i++)
            for (int j = 0; j < W; j++)
                scanf("%d", &map[i][j]);
        dfs(0);
        printf("#%d %d\n", tc, dab);
    }
    return 0;
}