[ 백준 3187 ] 양치기 꿍 (C++)

백준의 양치기 꿍(3187) 문제이다.

[ 문제 바로가기 ]

[ 문제풀이 ]

1) 사실 이 문제는 3184번 양 문제와 똑같은 문제이다. 단지, 양을 맵에서 표현하는 것이 o, k로 다르게 표현됬을 뿐 구현해야 하는

   내용은 똑같다.

   [ 3184번 양 문제 바로가기 ]

   이 문제는 BFS로 쉽게 해결할 수 있다. 모든 정점에서, BFS를 실행시키되, 중복탐색을 방지하기 위해서 아직 한번도 탐색하지

   않은 정점에 대해서 BFS를 실행시키면 된다.

   왜 그런지 알아보자.

   이러한 맵이 있다고 가정해보자.(왼쪽 가장 위는 (0,0), 오른쪽 가장 아래는 (4,4)로 표현하겠다)

   모든 정점에서 BFS를 실행시킨다고 생각해보자. 그럼 가장 먼저, (0, 0)에서 BFS가 실행될 것이다.

   BFS에서는 당연히 '#'으로표시된 부분은 탐색을 하지 못할 것이고, '.' 혹은 양과 늑대가 있는 정점들만 탐색을 할 것이다.

   따라서, 위의 맵에서는 (0, 0), (0, 1), (0, 2), (0, 3)을 (0, 0)으로 시작한 BFS에서 탐색을 할 것이다.

   이 후, BFS가 종료된 후, 그 다음 BFS가 실행되는 정점은 (2, 0)일 것이다. 마찬가지로, ~(2, 3)까지 탐색을 할 것이다.

   즉, BFS에서 갈 수 있는 정점은 모두 가보기 때문에, 이미 탐색한 정점은 또 방문할 필요가 없다.

2) 그렇다면 BFS 안에서는 어떤 내용을 구현해줘야 할지 알아보자.

   한 영역 안에서, 양 > 늑대 일 경우, 양이 살아남고 늑대가 모두 죽게된다. 즉, 우리는 양의 갯수를 Count하는 변수와, 늑대의 수

   를 Count해줘야 한다. BFS를 탐색하면서, 이 값들을 Count해준 후, BFS가 종료되면 이 2개의 값을 비교해서 누가 살아남는지를

   판단해야 한다. 만약 양 > 늑대 일 경우, 전체 양의 갯수에 현재 울타리의 양의 갯수를 +시켜줘야 하고, 그 반대의 경우에는

   늑대의 수를 +해줘야 한다.

 

   즉, 우리는 정답도출을 위해서, 전체 양의수를 저장하는 변수와, 전체 늑대의수를 저장하는 변수를 만들어 줘야 하고,

   각 영역마다 양의수와 늑대의수를 저장하는 변수를 만들어서 관리해줘야 한다.

[ 소스코드 ]

#include<iostream>
#include<queue>
 
#define endl "\n"
#define MAX 250
using namespace std;
 
int R, C, Total_Sheep, Total_Wolf;
char MAP[MAX][MAX];
bool Visit[MAX][MAX];
 
int dx[] = { 0, 0, 1, -1 };
int dy[] = { 1, -1, 0, 0 };
 
void Input()
{
    cin >> R >> C;
    for (int i = 0; i < R; i++)
    {
        for (int j = 0; j < C; j++)
        {
            cin >> MAP[i][j];
        }
    }
}
 
void BFS(int a, int b)
{
    int Cur_Sheep, Cur_Wolf;
    Cur_Sheep = Cur_Wolf = 0;
    queue<pair<int, int>> Q;
    Q.push(make_pair(a, b));
    Visit[a][b] = true;
 
    if (MAP[a][b] == 'k') Cur_Sheep++;
    if (MAP[a][b] == 'v') Cur_Wolf++;
 
    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 < R && ny < C)
            {
                if (Visit[nx][ny] == false)
                {
                    if (MAP[nx][ny] == '.')
                    {
                        Visit[nx][ny] = true;
                        Q.push(make_pair(nx, ny));
                    }
                    else if (MAP[nx][ny] == 'v')
                    {
                        Visit[nx][ny] = true;
                        Q.push(make_pair(nx, ny));
                        Cur_Wolf++;
                    }
                    else if (MAP[nx][ny] == 'k')
                    {
                        Visit[nx][ny] = true;
                        Q.push(make_pair(nx, ny));
                        Cur_Sheep++;
                    }
                }
            }
        }
    }
 
    if (Cur_Sheep > Cur_Wolf) Total_Sheep = Total_Sheep + Cur_Sheep;
    else Total_Wolf = Total_Wolf + Cur_Wolf;
}
 
void Solution()
{
    for (int i = 0; i < R; i++)
    {
        for(int j = 0; j < C; j++)
        {
            if (MAP[i][j] == '#') continue;
            if (Visit[i][j] == false)
            {
                BFS(i, j);
            }
        }
    }
 
    cout << Total_Sheep << " " << Total_Wolf << 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;
}