3187. 양치기 꿍

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

3187번: 양치기 꿍

 

요점

1. 울타리는 #, 양은 k, 늑대는 v

2. 울타리 내부에 양의 수가 늑대의 수보다 많으면 늑대가 모두 잡아먹힌다.

3. 울타리 내부에 늑대의 수가 양의 수보다 많으면 양이 모두 잡아먹힌다.

 

Solution

1. 영역별로 살펴보기 위해 배열값이 #이 아닌경우 bfs를 해서 양의 수와 늑대 수를 계산한다.

 

2. 영역 내부값만 BFS로 살펴보고, 내부값이 v면 wolf를 더해주고 k면 sheep을 더해준다.

 

3. BFS를 통해 영역을 모두 살펴본 후, 늑대가 많으면 양이 모두 잡아먹히니 ansW에 늑대 수(wolf)를 더해주고 양이 많으면 늑대가 모두 잡아먹히니 ansS에 양의 수(sheep)를 더해준다.

 

 

소스 코드

#include <iostream>
#include <vector>
#include <algorithm>
#include <utility>
#include <queue>
#define FASTio ios_base :: sync_with_stdio(false), cin.tie(NULL), cout.tie(NULL)
#define endl '\n' 

using namespace std;
int n,m;
vector<vector<char>> area(250,vector<char>(250));
vector<vector<bool>> check(250,vector<bool>(250));

int dy[]={-1,1,0,0};
int dx[]={0,0,1,-1};
int ansS =0;
int ansW =0;


void bfs(int y,int x)
{   
    int sheep = 0;
    int wolf = 0;
    queue<pair<int,int>> q;

    q.push(make_pair(y,x));
    check[y][x]=true;

    if(area[y][x]=='v') wolf++;
    else if(area[y][x]=='k') sheep++;


    while(!q.empty())
    {
        int y = q.front().first;
        int x = q.front().second;

        q.pop();

        for(int i=0;i<4;i++)
        {
            int ny = y + dy[i];
            int nx = x + dx[i];
            
            if(ny>=0 && nx>=0 && ny<n && nx<m && area[ny][nx]!='#')
            {
                if(check[ny][nx]==false)
                {
                    if(area[ny][nx]=='v')
                    {
                        wolf++;
                        check[ny][nx] = true;
                        q.push(make_pair(ny,nx));
                    }

                    else if(area[ny][nx]=='k')
                    {
                        sheep++;
                        check[ny][nx] = true;
                        q.push(make_pair(ny,nx));
                    }
                    else if(area[ny][nx]=='.')
                    {
                        check[ny][nx] = true;
                        q.push(make_pair(ny,nx));
                    }

                }
            }
        }
    }

    if(sheep>wolf)
    {
        wolf = 0;
    }
    else
    {
        sheep = 0;
    }

    ansS += sheep;
    ansW += wolf;

}
int main()
{
    FASTio;
    cin >> n >> m;

    for(int i=0;i<n;i++)
    {
        for(int j=0;j<m;j++)
        {
            cin >> area[i][j];
        }
    }

    for(int i=0;i<n;i++)
    {
        for(int j=0;j<m;j++)
        {    
            if(area[i][j]!='#' && check[i][j]==false)
            {
                bfs(i,j);
            }
        }
    }

    cout << ansS << ' ' << ansW;
    return 0;
}