[ SWEA 5656 ] 벽돌깨기 (C++)

SWExpertAcademy의 벽돌깨기(5656) 문제이다.

[ 문제풀이 ]

1) 상당히 난이도가 있었던 문제였다. 천천히 하나하나 진행해보도록 하자.

   본인은 이 문제를 '완전탐색' 으로 진행해주었다. 구슬을 어디에 쏴야할지 모르기 때문에 구슬을 쏠 수 있는 모든 경우에 대해서

   탐색을 다 해보는 것이다.

   그럼 예를들어서 3개의 구슬을 쏠건데, 맵이 5(세로)x5(가로) 형태라고 생각해보자. 이 경우를 완전탐색으로 구슬을 발사할 경우

   어느어느 경우가 생길지 생각해보자.

   { 첫번째 구슬이 발사하는 열, 두번째 구슬이 발사하는 열, 세번째 구슬이 발사하는 열 } 로 나열해보면

   { 0, 0, 0 } , { 0, 0, 1 } , { 0, 1, 0 } .... { 4, 4, 3 } , { 4, 4, 4 } 와 같은 수없이 많은 경우가 나올 것이다.

   그럼 저 모든 경우를 어떻게 구할까?? 잘보면 위의 결과는, 5개중에 3개를 뽑는 '중복순열'과 같다는 것을 눈치챌 수 있다.

   왜 중복순열일까?? 그전에 중복순열이 뭘까??

   중복순열이라는 것은 '순서과 상관이 있으면서 중복되게 값을 뽑을 수 있는 수열' 을 의미한다.

   그렇다면 왜 중복순열일까??

   일단 중복인 이유는 쉽게 알 수 있다. 3개의 구슬중에서 하나의 구슬이 0열에 발사했다고 하더라도, 그 다음 구슬이 0열에

   발사를 못하는게 아니기 때문이다. 3개의 구슬 모두 0열에 발사할 수도 있다.

   그렇다면 왜 순열일까?? 왜 순서가 상관이 있을까??

   1번구슬을 0열에 발사하고 2번구슬을 1열에 발사하고 3번구슬을 2열에 발사하는 경우와

   1번구술을 2열에 발사하고 2번구슬을 0열에 발사하고 3번구슬을 1열에 발사하는 경우를 생각해보자.

   전자는 { 0, 1, 2 } 이고 후자는 { 2, 0, 1 }이다. 이 경우에 결과가 다르게 나오기 때문이다.

   첫 번째 구슬을 0번째 열에 발사함으로써 터지는 벽돌과, 2번째 열에 발사함으로써 터지는 벽돌은 서로 다르기 때문이다.

   즉, 순서에 영향을 미치는 '중복순열' 이라는 것을 우리는 알아낼 수 있다.

   아직 중복순열에 대해서 잘 모른다면 아래의 글을 읽고 오도록 하자.

   [ 중복순열 알아보기 바로가기(Click) ]

   

   그렇다면 우리 문제에서는 몇개중에 몇개를 뽑아서 중복순열로 만들어줘야할까??

   바로 W개 중에 N개를 뽑는것이다. 문제에서 W는 가로의 길이, 즉 열을 의미하고 N은 발사할 구슬의 갯수를 의미한다.

   즉, 우리는 총 열의 갯수에서 구슬의 갯수만큼 중복순열로 뽑아서 완전탐색을 진행할 수 있다.

2) 중복순열을 구현함으로써 N개의 구슬을 어디어디에 쏠지 정해졌다고 하자. 그렇다면 이젠 무엇을 해줘야할까??

   실제로 벽돌을 깨보면 된다. 그 전에 문제를 확실히 이해하자.

   문제에서는 "가장 많은 벽돌을 깨고 싶을 때 남은 벽돌의 갯수를 구해라" 라고 하였다.

   즉, 우리가 구해야할 것은 남은 벽돌의 최소갯수를 구하면 된다. 가장 많은 벽돌을 깬다는 것은 남은 벽돌이 가장 적다는

   의미이기 때문이다.

  

   실제로 벽돌을 부수는 부분은 본인은 재귀로 구현하였다. 이게 연쇄적으로 벽돌이 깨져버리기 때문에, 벽돌을 깨지는

   과정에서 그 벽돌에 의해서 깨지는 벽돌까지 모두 계산해주기 위해서 재귀를 사용해주었다.

   재귀는 언제나 그렇듯 말로 설명하기 어려우니 일단 코드를 보고 차례차례 알아가보자.

void DFS(int x, int y)
{
    Visit[x][y] = true;
    int K_Value = C_MAP[x][y] - 1 ;
   
    for (int i = 0; i < 4; i++)
    {
        for (int k = 1; k <= K_Value; k++)
        {
            int nx = x + dx[i] * k;
            int ny = y + dy[i] * k;
           
            if (nx >= 0 && ny >= 0 && nx < H && ny < W)
            {
                if (Visit[nx][ny] == false && C_MAP[nx][ny] != 0)
                {
                    DFS(nx, ny);
                    C_MAP[nx][ny] = 0;
                }
            }
        }
    }
    C_MAP[x][y] = 0;
}

   본인이 벽돌을 연쇄적으로 뿌수기 위해서 사용한 DFS함수이다.

   먼저 중복된 방문을 제거하기 위한 2차원 배열 Visit에 방문 시, 방문했다는 체크를 해주었다.

   이 후에 해당 칸의 숫자만큼에 있는 벽돌들을 모두 부셔주기 위해서 그 숫자의 칸만큼 계속해서 진행해준다.

   만약 이동한 칸의 값이 0이라면, 그 칸에서는 또 다른 연쇄로 부셔지는 일이 일어나지 않기 때문에 이동한 칸의 값이 0이

   아닐 때만 계산을 진행해준다. 이 후에 재귀가 빠지면서 값을 0으로 바꿔주면 된다.

   어차피 맵이 0으로 바뀔텐데, 그럼 Visit배열은 사용하지 않아도 되지 않을까 라는 생각이 들 수 있는데 이런 경우를 생각해보

   자.

  

   이 상황에서 Visit배열이 없다고 가정해보겠다.

   가장 왼쪽 2가 폭팔해서 옆에 2로 번져가는 상황이라고 생각해보자. 또한, dx dy의 순서가 { 동 서 남 북 } 이라고 가정하겠

   다. 먼저 가장 왼쪽에서 2에서 가운데 2로 번져 나갈 것이다. (동서남북 순서에 의해서 가장 먼저 동쪽으로 퍼짐)

   가운데 2에서는 또 동쪽으로 퍼져나갈 텐데, 오른쪽이 0이기 때문에 별다른 재귀호출 없이 그다음 방향인 서쪽을 향하게 된

   다. 서쪽은 또 2가 있기 때문에 다시 왼쪽 2에서 동쪽으로 탐색을 시작할 것이고, 또 똑같은 2를 만나게 되고 위와 같은 상황을

   반복하게 된다. 즉, 재귀가 끝없이 반복될 수 있기 때문이다. 이래서 Visit배열이 필요하다.

   위와 같은 과정으로 모든 구슬이 해당 벽을 뿌술 때 까지 반복한다. 모든 구슬이 모두 폭팔했다면, 이제는 맵을 정리해주어야

   한다. 분명히 공중에 떠있는 벽돌들이 존재할 것이기 때문이다. ( 이 부분은 별다른 설명보단 소스코드 참고 )

   이렇게 모든 경우를 다 탐색해서 최소값을 비교해주면 된다.

   이 과정에서 본인은 하나의 예외적인 케이스일 경우에는 탐색을 더 이상 진행하지 않고 종료해주었다.

   그 케이스가 바로 구슬을 발사해서 벽돌을 부셔봤는데, 남은 벽돌의 갯수가 0일 때이다.

   어떤 경우더라도 벽돌의 갯수가 0개 보다 작을 수는 없다. 따라서, 본인은 벽돌의 갯수가 0이 나오게 되면 탐색을 종료하는

   조건문을 걸어주었다. (사실 이 부분은 안해도 무관한데, 이 부분을 구현하면 시간이 훨씬 더 빨라진다)

[ 소스코드 ]

#include<iostream>
#include<cstring>
 
#define endl "\n"
#define MAX 10
using namespace std;
 
bool Already_Answer;
int N, W, H, Answer;
int MAP[15][12];
int C_MAP[15][12];
bool Visit[15][12];
int Select[12];
 
int dx[] = { 0, 0, 1, -1 };
int dy[] = { 1, -1, 0, 0 };
 
int Min(int A, int B) { if (A < B) return A; return B; }
 
void Initialize()
{
    Already_Answer = true;
    Answer = 987654321;
    memset(Visit, false, sizeof(Visit));
    memset(MAP, 0, sizeof(MAP));
    memset(Select, false, sizeof(Select));
}
 
void Input()
{
    cin >> N >> W >> H;
    for (int i = 0; i < H; i++)
    {
        for (int j = 0; j < W; j++)
        {
            cin >> MAP[i][j];
            if (MAP[i][j] != 0) Already_Answer = false;
        }
    }
}
 
void Copy_MAP()
{
    for (int i = 0; i < H; i++)
    {
        for (int j = 0; j < W; j++)
        {
            C_MAP[i][j] = MAP[i][j];
        }
    }
}
 
void Print()
{
    cout << "##########################################" << endl;
    for (int i = 0; i < H; i++)
    {
        for (int j = 0; j < W; j++)
        {
            cout << C_MAP[i][j] << " ";
        }
        cout << endl;
    }
    cout << "##########################################" << endl;
 
}
 
void DFS(int x, int y)
{
    Visit[x][y] = true;
    int K_Value = C_MAP[x][y] -1;
 
    for (int i = 0; i < 4; i++)
    {
        for (int k = 1; k <= K_Value; k++)
        {
            int nx = x + dx[i] * k;
            int ny = y + dy[i] * k;
            
            if (nx >= 0 && ny >= 0 && nx < H && ny < W)
            {
                if (Visit[nx][ny] == false && C_MAP[nx][ny] != 0)
                {
                    DFS(nx, ny);
                    C_MAP[nx][ny] = 0;
                }
            }
        }
    }
    C_MAP[x][y] = 0;
}
 
void Remake_MAP()        // 맵을 다시 정리하는 함수.
{
    for (int i = H - 1; i > 0; i--)
    {
        for (int j = 0; j < W; j++)
        {
            bool Check = false;
            if (C_MAP[i][j] == 0)
            {
                int Temp_I = i - 1;
 
                while (Temp_I >= 0)
                {
                    if (C_MAP[Temp_I][j] != 0)
                    {
                        Check = true;
                        break;
                    }
                    Temp_I--;
                }
 
                if (Check == true)
                {
                    C_MAP[i][j] = C_MAP[Temp_I][j];
                    C_MAP[Temp_I][j] = 0;
                }
            }
        }
    }
}
 
int Count()
{
    int Cnt = 0;
    for (int i = 0; i < H; i++)
    {
        for (int j = 0; j < W; j++)
        {
            if (C_MAP[i][j] != 0) Cnt++;
        }
    }
    return Cnt;
}
 
bool Check_MAP_State()
{
    for (int i = 0; i < H; i++)
    {
        for (int j = 0; j < W; j++)
        {
            if (C_MAP[i][j] != 0) return false;
        }
    }
    return true;
}
 
void Drop_The_Ball()
{
    for (int i = 0; i < N; i++)
    {
        memset(Visit, false, sizeof(Visit));
        int Idx = Select[i];            // Idx = 구슬이 날아갈 열의 위치.
        bool Flag = false;                // 구슬에 의해서 무언가가 폭팔했는지 판단하기 위한 함수.
 
        for (int j = 0; j < H; j++)
        {
            if (C_MAP[j][Idx] != 0)
            {
                Flag = true;
                DFS(j, Idx);            // 구슬에 의한 벽돌 연쇄적인 제거를 위한 DFS
                break;
            }
        }
        if (Check_MAP_State() == true)    // 예외 Case. 남은 벽돌이 0개라면 탐색 더이상 불필요.
        {
            Already_Answer = true;
            return;
        }
        if (Flag == true) Remake_MAP();    // 구슬에 의해서 아무것도 폭팔하지 않았다면 MAP을 정리할 필요가 없음.
    }
 
    Answer = Min(Answer, Count());
}
 
void Select_Position(int Cnt)
{
    if (Already_Answer == true)    // 예외적인 Case. 벽돌이 0개가 되는 경우라면 더이상 탐색 불필요.
    {
        Answer = 0;
        return;
    }
    if (Cnt == N)                // 중복순열 종료조건.
    {
        Copy_MAP();                // 맵의 형태가 바뀌므로 맵 복사 후 진행
        Drop_The_Ball();        // 구슬 날리기 !
        return;
    }
 
    for (int i = 0; i < W; i++)
    {
        Select[Cnt] = i;
        Select_Position(Cnt + 1);
    }
}
 
void Solution()
{
    if (Already_Answer == true)    // 벽돌이 한개도 없을 시 탐색 필요없이 바로 0 return.
    {
        Answer = 0;
        return;
    }
    Select_Position(0);            // 중복순열을 통해서 구슬을 어디에 날리지 뽑기.
}
 
void Solve()
{
    int Tc; cin >> Tc;
    for (int T = 1; T <= Tc; T++)
    {
        Initialize();
        Input();
        Solution();
        
        cout << "#" << T << " " << Answer << endl;
    }
}
 
int main(void)
{
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
 
    freopen("Input.txt", "r", stdin);
    Solve();
 
    return 0;
}