[ 백준 16988 ] Baaaaaaaaaduk2 (Easy) (C++)

백준의 Baaaaaaaaaaduk2(Easy)(16988) 문제이다.

[ 문제 바로가기 ]

[ 문제풀이 ]

1) 본인은 이 문제를 구현하기 위해서 다음과 같은 순서로 로직을 생각해 보았다.

   1. 2개의 돌을 놓을 만한 좌표들의 후보 정하기

   2. 조합 구현하기

   3. 죽일 수 있는 상대 돌의 갯수를 Count 후, 갱신하기

   먼저 1번 과정부터 예제입력 1을 통해서 알아보자.

  

   위와 같이 맵이 존재한다. 그런데 위의 맵에서 과연 다음과 같이 표시된 좌표에 돌을 놓아보는게 의미가 있을지 생각을

   해보자.

  

   바로 빨강색 * 로 표시된 좌표들이다. 저 좌표들 중에서 2개를 선택해서, 돌을 놓아보는 것이 과연 의미가 있을까 ??

   의미가 없다. 왜냐하면 주변에 상대방의 돌이 없기 때문에, 저 위치에 돌을 놓는다고 해서 상대방의 돌을 죽일 수

   없다.

   따라서, 본인은 모든 비어있는 좌표를 탐색하면서, 상하좌우 총 4방향 중에 최소 1개 이상의 상대방 돌이 있는 좌표들만

   '돌을 놓았을 때, 상대방 돌을 죽일 만한 좌표' 라 생각하고 이 좌표들만 따로 Vector에 저장을 해 주었다.

   2번 과정은 조합 구현하기이다. 바로 위에서 구한, 상대방을 죽일만한 좌표들 중에서 2개를 뽑는 조합을 구현하였다.

   왜 조합일까 ??

  

   위의 좌표에서, 알파벳으로 표시된 부분이 아마 상대방의 돌을 죽일만한 후보 좌표들이 될 것이다.

   그런데, 이 후보 좌표들 중에서 예를 들어 { A, B } 이렇게 2개를 뽑았다고 가정해보자.

   이렇게 2개를 뽑았을 때, 과연 { B, A }를 뽑았을 때와 결과가 다를까 ?? 같을 것이다. 따라서, 순서에 영향을 미치지 않는

   수열을 만들어야 하기 때문에 '조합'을 구현해 주었다.

   아직 조합을 모른다면 아래의 글을 읽고 오도록 하자.

   [ 조합에 대해서 알아보기 (Click) ]

   3번 과정은 2번 과정에서 구한 2개의 좌표들에 직접 아군 돌을 놓아보고, 적군을 최대 몇개 죽일 수 있는지 확인해보는

   과정이다. 본인은 이 과정에서 너비우선탐색(BFS) 기법을 사용했다. 어떻게 사용했는지 지금부터 알아보자.

  

    위와 같은 상황을 생각해보자. 위의 상황에서 표시했듯이, 아군 돌을 놓아볼만한 후보가 되는 좌표는 A, B, C, D 4개의

    좌표가 있다. 그럼 2개의 조합을 뽑는 과정에서 { A, B } 를 뽑아서 이 두 좌표에 아군돌을 놓았다고 생각해보자.

    그럼 아마 저기 3개가 붙어있는 적군돌을 먹을 수 있게 된다.

    본인은 적군돌이 위치 하는 좌표에서 'BFS' 탐색을 진행해 주었다.

    A와 B에 아군돌을 놓은 상태이고, A와 B사이에 있는 적군돌에서 상하좌우로 움직이면서 아군돌이 있지 않은 좌표로만

    탐색을 진행한다면 어떻게 될까 ??

    아마 A와 B사이에 있는 '2' 에서 출발해서, 남쪽에 있는 '2'를 방문하고, 그 후 동쪽에 있는 '2'를 방문하고 탐색을

    종료하게 될 것이다. 이렇게 정상적으로 탐색이 종료될 경우 잡아먹을 수 있음을 의미한다.

    그럼 { A, C } 2개의 좌표를 뽑았다고 생각해보자. 그림으로 보자면 다음과 같이 뽑은 상태일 것이다.

   

    이렇게 있기 때문에, (0, 2), (1, 2), (1, 3)에 존재하는 3개의 '2'를 먹을 수 없게 된다.

    왜 ?? (0, 3)에 빈 칸이 있기 때문에 이 돌들은 포위되지 않은 상태가 되기 때문이다.

    즉 ! BFS탐색을 적군의 좌표에서 시작하는데, '1'이 아닌 좌표라면 무조건 탐색을 진행한다. 하지만 ! 탐색 도중에

    빈칸을(0인 좌표) 만나게 되면, 이는 죽지 않는다는 의미이다. 따라서, 이 경우에는 0을 반환하도록 구현해 주었다.

   

[ 소스코드 ]

#include<iostream>
#include<vector>
#include<cstring>
#include<queue>
 
#define endl "\n"
#define MAX 20
using namespace std;
 
int N, M, Answer;
int MAP[MAX][MAX];
bool Select[MAX * MAX];
bool Visit[MAX][MAX];
vector<pair<int, int>> T_Empty, Empty, Enemy;
 
int dx[] = { 0, 0, 1, -1 };
int dy[] = { 1, -1, 0, 0 };
 
int Bigger(int A, int B) { if (A > B) return A; return B; }
 
void Input()
{
    cin >> N >> M;
    for (int i = 0; i < N; i++)
    {
        for (int j = 0; j < M; j++)
        {
            cin >> MAP[i][j];
            if (MAP[i][j] == 0) T_Empty.push_back(make_pair(i, j));
            else if (MAP[i][j] == 2) Enemy.push_back(make_pair(i, j));
        }
    }
}
 
int BFS(int a, int b)
{
    int Cnt = 0;
    queue<pair<int, int>> Q;
    Q.push(make_pair(a , b));
    Visit[a][b] = true;
    bool Flag = true;
    Cnt++;
 
    while (Q.empty() == 0)
    {
        int x = Q.front().first;
        int y = Q.front().second;
        Q.pop();
 
        for (int i = 0; i < 4; i++)
        {
            int nx = x + dx[i];
            int ny = y + dy[i];
            if (nx >= 0 && ny >= 0 && nx < N && ny < M)
            {
                if (MAP[nx][ny] == 2 && Visit[nx][ny] == false)
                {
                    Visit[nx][ny] = true;
                    Q.push(make_pair(nx, ny));
                    Cnt++;
                }
                else if (MAP[nx][ny] == 0) Flag = false;
            }
        }
    }
    if (Flag == true) return Cnt;
    return 0;
}
 
int Calculate()
{
    memset(Visit, false, sizeof(Visit));
    int Cnt = 0;
    for (int i = 0; i < Enemy.size(); i++)
    {
        int x = Enemy[i].first;
        int y = Enemy[i].second;
 
        if (Visit[x][y] == false) Cnt = Cnt + BFS(x, y);
    }
    return Cnt;
}
 
void DFS(int Idx, int Cnt)
{
    if (Cnt == 2)
    {
        int Res = Calculate();
        Answer = Bigger(Answer, Res);
        return;
    }
 
    for (int i = Idx; i < Empty.size(); i++)
    {
        if (Select[i] == true) continue;
        Select[i] = true;
        MAP[Empty[i].first][Empty[i].second] = 1;
        DFS(i, Cnt + 1);
        MAP[Empty[i].first][Empty[i].second] = 0;
        Select[i] = false;
    }
}
 
void Find_Candidate()
{
    for (int i = 0; i < T_Empty.size(); i++)
    {
        int x = T_Empty[i].first;
        int y = T_Empty[i].second;
 
        for (int j = 0; j < 4; j++)
        {
            int nx = x + dx[j];
            int ny = y + dy[j];
            if(nx >=0 && ny >=0 && nx < N && ny < M)
            { 
                if (MAP[nx][ny] == 2)
                {
                    Empty.push_back(make_pair(x, y));
                    break;
                }
            }
        }
    }
}
 
void Solution()
{
    Find_Candidate();
    DFS(0, 0);
    cout << Answer << endl;
}
 
void Solve()
{
    Input();
    Solution();
}
 
int main(void)
{
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
 
    //freopen("Input.txt", "r", stdin);
    Solve();
 
    return 0;
}