5656. 벽돌깨기

5656.벽돌깨기

이게 맞나 싶을 정도로 지저분하게 푼 것 같다...

일단 기본적으로 완전탐색 + 시뮬레이션 문제 같은데.. 시뮬레이션을 엄청 지저분하게 푼 것 같다..

기본적인 흐름은, 구슬을 최대 4번까지 할 수 있으므로 가로축에서 모두 굴려보는 방식의 완전탐색을 이용했다.

나한테 까다로운 부분을 시뮬레이션 부분이었는데.. 이 부분은 분할정복과 흡사하게 재귀를 이용하였다..

혹시 스택오버플로우가 나지 않을까 했는데 역시나 스택오버플로우가 발생하였다.

makeMap() 이라는 함수 부분에서 분할정복 재귀를 이용하였는데, 구슬이 오는 시작점을 기준으로 상,하,좌,우 를 모두 하나씩 이동하면서 그 

그 이동하는 지점에서 다시 재귀함수를 실행하도록 구현하였다.

스택오버플로우는 범위값 지정해주고, 0일때는 재귀함수를 바로 빠져나오도록 해서 스택오버플로우를 해결할 수 있었다..

뭔가 너무 지저분해서 깔끔한 아이디어를 찾아봐야겠다...

아하..! 다른 사람들 아이디어를 좀 보니까.. 이거는 BFS 나 DFS를 이용해서 벽돌을 깨면 더 쉬울 것 같다. 맵의 정점을 하나의 노드라고 생각

한다면, 연결된 모든 노드들을 모두 방문하면서 제거하면 된다! 

정답 코드로 DFS와 BFS를 이용한 해결법도 수정해서 올렸다

<정답 코드 (수정 후)>

#include<iostream>
#include<queue>
using namespace std;
 
typedef struct pos {
    int x;
    int y;
    int d;
}pos;
 
int N, W, H;
int ans;
int map[15][12];
 
int dx[4] = { 0,0,1,-1 };
int dy[4] = { 1,-1,0,0 };
 
 
 
bool check_range(int x, int y)
{
    if (x >= 0 && y >= 0 && x < H && y < W)
        return true;
    else
        return false;
 
}
 
//DFS 로 벽 부수기
void breakWall(int x, int y)
{
    if (map[x][y] == 0)
        return;
 
    int d = map[x][y];
    map[x][y] = 0;
 
    for (int i = 1; i < d; i++)
    {
        for (int j = 0; j < 4; j++)
        {
            int nx = x + dx[j] * i;
            int ny = y + dy[j] * i;
 
            if (check_range(nx, ny) && map[nx][ny] != 0)
                breakWall(nx, ny);
        }
    }
}
 
//BFS로 벽 부수기
void breakWall2(int x, int y,int d)
{
 
    queue<pos> q;
    pos p = { x,y,d };
    q.push(p);
    map[x][y] = 0;
 
    while (!q.empty())
    {
        int curx = q.front().x;
        int cury = q.front().y;
        int d = q.front().d;
        q.pop();
 
        for (int i = 1; i < d; i++)
        {
            for (int j = 0; j < 4; j++)
            {
                int nx = curx + dx[j] * i;
                int ny = cury + dy[j] * i;
                int nd = map[nx][ny];
 
                if (check_range(nx, ny) && map[nx][ny] != 0)
                {
                    pos tmp = { nx,ny,nd };
                    map[nx][ny] = 0;
                    q.push(tmp);
                }
            }
        }
 
    }
    
}
 
//맵 정렬
void allign_map()
{
 
    for (int i = 0; i < W; i++)
    {
        for (int j = H - 2; j >= 0; j--)
        {
            int x = j, y = i;
 
            if (map[x][y] == 0)
                continue;
 
            while (true)
            {
                if (map[x + 1][y] == 0 && check_range(x + 1, y))
                {
                    map[x + 1][y] = map[x][y];
                    map[x][y] = 0;
                    x++;
                }
                else
                    break;
            }
        }
    }
 
}
 
// 배열 복사
void copy(int(*from)[12], int(*to)[12])
{
    for (int i = 0; i < 15; i++)
        for (int j = 0; j < 12; j++)
            to[i][j] = from[i][j];
}
 
//떨어지는 위치 정하기
void go(int k)
{
    int tmp[15][12];
    copy(map, tmp);
 
 
    if (k == N)
    {
        int cnt = 0;
        for (int i = 0; i < H; i++)
            for (int j = 0; j < W; j++)
                if (map[i][j] != 0)
                    cnt++;
 
        if (cnt < ans)
            ans = cnt;
 
        return;
    }
 
    for (int i = 0; i < W; i++)
    {
 
        int x = 0, y = i;
        while (check_range(x, y) && map[x][y] == 0)
            x++;
 
        //breakWall(x, y);
        breakWall2(x, y, map[x][y]);
        allign_map();
        go(k + 1);
        copy(tmp, map);
 
 
    }
}
int main()
{
 
    freopen("input.txt", "r", stdin);
 
    int tc;
    cin >> tc;
 
    for (int t = 1; t <= tc; t++)
    {
        cin >> N >> W >> H;
 
        ans = 987654321;
        for (int i = 0; i < H; i++)
            for (int j = 0; j < W; j++)
                cin >> map[i][j];
 
        go(0);
 
        cout << "#" << t << " " << ans << endl;
    }
 
 
 
    return 0;
}

<정답 코드>

#include<iostream>
#include<vector>
using namespace std;
 
int N, W, H;
int ans;
int map[15][12];
bool check_range(int x, int y)
{
    if (x >= 0 && y >= 0 && x < H && y < W)
        return true;
    else
        return false;
}
 
 
void makeMap(int x,int y)
{
    if (!check_range(x, y))
        return;
 
    if (map[x][y] == 0)
        return;
 
 
    int d = map[x][y];
 
    // 아래
    int tmp_x = x;
    int tmp_y = y;
    int tmp_d = d;
    while (true)
    {
        map[tmp_x][tmp_y] = 0;
        tmp_d--;
 
        if (tmp_d == 0)
            break;
 
        if (!check_range(tmp_x+1, tmp_y))
            break;
 
        if (map[tmp_x + 1][tmp_y] > tmp_d)
            tmp_d = map[tmp_x + 1][tmp_y];
 
        tmp_x++;
        makeMap(tmp_x, tmp_y);
    }
 
    // 오른쪽
 
    tmp_x = x;
    tmp_y = y;
    tmp_d = d;
    while (true)
    {
        map[tmp_x][tmp_y] = 0;
        tmp_d--;
        if (tmp_d == 0)
            break;
 
        if (!check_range(tmp_x, tmp_y+1))
            break;
 
        if (map[tmp_x][tmp_y+1] > tmp_d)
            tmp_d = map[tmp_x][tmp_y+1];
 
        tmp_y++;
        makeMap(tmp_x, tmp_y);
    }
 
    //왼쪽
 
    tmp_x = x;
    tmp_y = y;
    tmp_d = d;
    while (true)
    {
        map[tmp_x][tmp_y] = 0;
        tmp_d--;
        if (tmp_d == 0)
            break;
 
        if (!check_range(tmp_x, tmp_y-1))
            break;
 
        if (map[tmp_x][tmp_y-1] > tmp_d)
            tmp_d = map[tmp_x][tmp_y-1];
 
        tmp_y--;
        makeMap(tmp_x, tmp_y);
    }
 
    // 위쪽
    tmp_x = x;
    tmp_y = y;
    tmp_d = d;
    while (true)
    {
        map[tmp_x][tmp_y] = 0;
        tmp_d--;
        if (tmp_d == 0)
            break;
 
        if (!check_range(tmp_x-1, tmp_y))
            break;
 
        if (map[tmp_x - 1][tmp_y] > tmp_d)
            tmp_d = map[tmp_x - 1][tmp_y];
 
        tmp_x--;
        makeMap(tmp_x, tmp_y);
    }
 
 
}
void allign_map()
{
    // 빈칸 정렬
    for (int i = 0; i < W; i++)
    {
        for (int j = H - 2; j >= 0; j--)
        {
            if (map[j][i] == 0)
                continue;
 
            int x = j, y = i;
 
            while (true)
            {
                if (map[x + 1][y] == 0 && check_range(x + 1, y))
                {
                    map[x + 1][y] = map[x][y];
                    map[x][y] = 0;
                    x++;
                }
                else
                    break;
            }
 
        }
    }
}
void go(int k)
{
    // 구슬 다 쐈을 때
    if (k == N)
    {
        int cnt = 0;
 
        for (int i = 0; i < H; i++)
        {
            for (int j = 0; j < W; j++)
            {
                if (map[i][j] != 0)
                    cnt++;
            }
        }
 
        if (cnt < ans)
            ans = cnt;
 
        return;
 
    }
 
 
    // 백트래킹을 위해 원래 맵 복사
    int tmp[15][12];
 
    for (int i = 0; i < H; i++)
    {
        for (int j = 0; j < W; j++)
        {
            tmp[i][j] = map[i][j];
        }
    }
 
    for (int i = 0; i < W; i++)
    {
 
        // 벽 터뜨릴 시작점 발견
        int x = 0, y = i;
        while (map[x][y] == 0 && check_range(x, y)) 
        {
            x++;
        }
 
        // 시작점으로 부터 벽 부시기 시작
        makeMap(x, y);
 
        // 부서진 벽들 정렬
        allign_map();
        go(k + 1);
 
 
        // 백트래킹
        for (int i = 0; i < H; i++)
        {
            for (int j = 0; j < W; j++)
            {
                map[i][j] = tmp[i][j];
            }
        }
        
    }
 
}
int main()
{
    //freopen("input.txt", "r", stdin);
    int tc;
    cin >> tc;
 
    for (int t = 1; t <= tc; t++)
    {
        ans = 987654321;
        cin >> N >> W >> H;
 
 
        for (int i = 0; i < H; i++)
        {
            for (int j = 0; j < W; j++)
            {
                cin >> map[i][j];
            }
        }
 
        go(0);
 
        cout << "#" << t << " " << ans << endl;
    }
 
    return 0;
}