boj 3184번 양

문제 링크 boj 3184번 양

문제 해석

주워진 영역 n x m의 영역은 울타리로 인하여 분리 되어있다.
각 영역에 늑대와 양이 있거나 아무것도 없는 빈 공간으로 있을 수 있다.

빈 공간 = '.'

울타리 = '#'

늑대 = 'v'

양 = 'o'

각 영역에 늑대의 수 >= 양의 수인 경우 양은 다 잡아먹혀서 0마리가 된다
각 영역의 양의 수 > 늑대의 수인 경우 양들이 늑대를 몰아내서 늑대가 0마리가 된다.

구하고자 하는 값 = 최종적으로 n x m영역에 살아 남아있는 늑대와 양의 수

#include <bits/stdc++.h>
#define X first
#define Y second
using namespace std;

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


int main(){
    ios::sync_with_stdio(0);
    cin.tie(0);

    int n,m;
    cin>>n>>m;

    string s[n]; // 문제 예제는 문자열을 줄바꿈으로 영역 주었기에 string 배열로 받았다.
    for(int i=0; i<n; i++){
        string ss;
        cin>>ss;
        s[i] =ss;
    }//입력받은 영역의 '#','.','v','o'채우기 완료

    int sheep=0,wolf=0; //최종 살아남을 양과 늑대

    for(int i=0; i<n; i++){
        for(int j=0; j<m; j++){
            queue<pair<int,int>> Q;
            int sp =0;
            int wf =0;
            if(s[i][j]!= '#'){//'#'이 아닌 곳은 나누어진 영역의 시작
                if(s[i][j]=='v') wf=1; //늑대가 있다면
                if(s[i][j]=='o') sp=1; // 양이 있다면
                Q.push({i,j});
                s[i][j] = '#';
            }
            while(!Q.empty()){//영역내부에 늑대와 양의 마리수 확인
                pair<int,int> cur = Q.front(); Q.pop();
                for(int z=0; z<4; z++){
                    int x = cur.X + dx[z];
                    int y = cur.Y + dy[z];
                    if(x<0||x>=n||y<0||y>=m)continue;
                    if(s[x][y]=='#')continue;
                    if(s[x][y]== 'v') wf++;
                    if(s[x][y]=='o') sp++;
                    Q.push({x,y});
                    s[x][y] = '#';
                }
            }
            if(sp>wf) wf=0;
            if(sp<=wf) sp =0;
            sheep+=sp;
            wolf+= wf;
        }
    }
    cout<<sheep<<" "<<wolf;
}