[ 백준 3184 ] 양 (C++)

백준의 양(3184) 문제이다.

( 문제 바로가기 )

[ 문제설명 ]

- 입력으로 행과 열의 크기가 주어지고, 맵이 하나 주어진다. 맵에서 o는 양을 v는 늑대를 의미한다.

- 한 영역(울타리에 막히지 않아서 움직일 수 있는 빈 공간이 2개이상 만나게 되는 곳) 안에 양의 수가 늑대의 수보다

  많으면 양이 살아남게 되고, 반대라면 늑대가 살아남게 된다.

- 이 때, 하루가 지나고 살아남은 양의 수와 늑대의 수를 구하는 문제이다.

[ 문제풀이 ]

1. 모든 정점에서 방문하지 않은 곳에 한해서 BFS를 모두 돌려보면 된다.

   BFS안에서는 늑대의 수와 양의 수를 Count할 수 있는 변수 2개만 따로 관리해주고 별다른 조건은 걸어주지 않아도 된다.

2. BFS가 끝나면 늑대의 수와 양의수를 비교해서 누가 살아남는지 판단하고, 살아남는 동물의 수를 + 해주면 된다.

3. 설명할 부분도 없고 코드를 보면 굉장히 쉽게 느껴질 것이다.

[ 소스코드 ]

#include<iostream>
#include<queue>
 
#define endl "\n"
#define MAX 250
using namespace std;
 
int R, C, Total_Wolf, Total_Sheep;
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 Wolf, Sheep;
    Wolf = Sheep = 0;
    queue<pair<int, int>> Q;
    Q.push(make_pair(a, b));
    Visit[a][b] = true;
 
    while (Q.empty() == 0)
    {
        int x = Q.front().first;
        int y = Q.front().second;
        Q.pop();
        
        if (MAP[x][y] == 'v') Wolf++;
        if (MAP[x][y] == 'o') Sheep++;
 
        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 (MAP[nx][ny] != '#' && Visit[nx][ny] == false)
                {
                    Visit[nx][ny] = true;
                    Q.push(make_pair(nx, ny));
                }
            }
        }
    }
 
    if (Sheep > Wolf) Total_Sheep = Total_Sheep + Sheep;
    else Total_Wolf = Total_Wolf + Wolf;
}
 
void Solution()
{
    for (int i = 0; i < R; i++)
    {
        for (int j = 0; j < C; j++)
        {
            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;
}