[백준 / BOJ / SILVER 2] 3184 번 : 양

https://www.acmicpc.net/problem/3184

3184번: 양

주어진 범위 안에 있는 각각의 울타리 내부의 양과 늑대의 수를 파악하여 조건에 따라 최종 양과 늑대 수를 출력하는 문제입니다.

 

아래는 코드입니다.

#include <iostream>
#include <queue>
 
using namespace std;
 
int R, C, Sheep = 0, Wolf = 0;
char Map[251][251];
bool Visit[251][251];
 
int dx[] = { 0,0,1,-1 };
int dy[] = { 1,-1,0,0 };
 
void Bfs(int a, int b)
{
    Visit[a][b] = true;
    int curSheep = 0, curWolf = 0;
    queue<pair<int, int>> q;
    q.push(make_pair(a, b));
    
    while (!q.empty())
    {
        int x = q.front().first;
        int y = q.front().second;
        q.pop();
 
        if (Map[x][y] == 'o')
        {
            curSheep++;
        }
        else if (Map[x][y] == 'v')
        {
            curWolf++;
        }
 
        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] != true)                // 좌표가 울타리가 아니면서, 방문한 적이 없는지를 확인 
                {
                    Visit[nx][ny] = true;                                        // nx, ny 좌표에 방문했다는 것을 체크
                    q.push(make_pair(nx, ny));                                     // queue에 nx,ny 값을 push함
                }
            }
        }
    }
 
    if (curSheep > curWolf)                                                         // 현재 양의 수를 체크하여 양이 더 많을 경우 양의 승리이므로 전체 늑대의 수에서 현재 체크한 늑대의 수만큼 감소시킴
    {
        Wolf -= curWolf;                                                        
    }
    else                                                                        // 반대의 경우 이므로 전체 양의 수에서 현재 체크한 양의 수만큼 
    {
        Sheep -= curSheep;
    }
}
 
int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(0);
 
    cin >> R >> C;
    for (int i = 0; i < R; i++)                                                    // 뒷마당에 양과 늑대, 울타리를 집어넣음
    {
        cin >> Map[i];
    }
 
    for (int i = 0; i < R; i++)                                                    // 뒷마당의 전체 양과 늑대의 수를 체크
    {
        for (int j = 0; j < C; j++)
        {
            if (Map[i][j] == 'o')
            {
                Sheep++;
            }
            else if (Map[i][j] == 'v')
            {
                Wolf++;
            }
        }
    }
 
    for (int i = 0; i < R; i++)
    {
        for (int j = 0; j < C; j++)
        {
            if (Visit[i][j] == false)
            {
                Bfs(i, j);
            }
        }
    }
 
    cout << Sheep << " " << Wolf << "\n";
 
    return 0;
}