3187번 양치기 꿍

입력을 받을때 양과 늑대의 위치를 큐에 넣어주고 bfs를 돌려 동시에 찾는다

 

늑대를 먼저 큐에서 빼든 양을 먼저 빼든 상관이 없다

 

큐에서 맨 처음 빼낸 좌표가 늑대인지 양인지 파악한 후 갯수를 1 더해주고 그 좌표를 기준으로 벽으로 막힌 곳까지 늑대와 양을 다 찾아낸다

 

찾아내서 누가 먼저 잡아먹히는지 비교해서 값에 넣어주고 큐에서 다음 늑대 혹은 양을 꺼내 확인한다

 

이때 방문처리를 통해 같은 공간에 있던 늑대 혹은 양인지 확인한 후 방문처리가 되어있으면 큐에서 그 다음 좌표를 꺼내 또 dfs를 시작한다

 

이 과정을 반복하여 늑대와 양의 수를 세게 된다.

 

#include <iostream>
#include <queue>
#define visited true
#define Non_visited false
#define MAX 251

using namespace std;

int xx[4]={1,0,-1,0};
int yy[4]={0,1,0,-1};
char cArr[MAX][MAX];
bool Check[MAX][MAX];
int Sheep;
int Wolf;
queue<pair<int,int>> SheepWolf;

void bfs(int M, int N){
    
    while(!SheepWolf.empty()){
        int xStart=SheepWolf.front().first;
        int yStart=SheepWolf.front().second;
        SheepWolf.pop();
        
        if(Check[xStart][yStart]) continue;
        Check[xStart][yStart]=visited;
        
        queue<pair<int,int>> q;
        q.push(make_pair(xStart,yStart));
        
        int sheep=0;
        int wolf=0;
        
        if(cArr[xStart][yStart]=='k') sheep++;
        if(cArr[xStart][yStart]=='v') wolf++;
        
        while(!q.empty()){
            int x=q.front().first;
            int y=q.front().second;
            q.pop();
            
            for(int i=0;i<4;i++){
                int nx=x+xx[i];
                int ny=y+yy[i];
                
                if(nx<0 || nx>=M || ny<0 || ny>=N || cArr[nx][ny]=='#' || Check[nx][ny]) continue;
                if(cArr[nx][ny]=='k'){
                    Check[nx][ny]=visited;
                    sheep++;
                }
                if(cArr[nx][ny]=='v'){
                    Check[nx][ny]=visited;
                    wolf++;
                }
                if(cArr[nx][ny]=='.'){
                    Check[nx][ny]=visited;
                }
                q.push(make_pair(nx,ny));
            }
        }
        if(sheep>wolf){
            Sheep+=sheep;
        }
        else
            Wolf+=wolf;
    }
    
//    while(!sheep.empty()){
//        int x=sheep.front().first;
//        int y=sheep.front().second;
//        sheep.pop();
//
//        if(Check[x][y]) continue;
//
//        Check[x][y]=visited;
//
//        for(int i=0;i<4;i++){
//            int nx=x+xx[i];
//            int ny=y+yy[i];
//
//            if(nx<0 || nx>=M || ny<0 || ny>=N || cArr[nx][ny]=='#') continue;
//            if(cArr[nx][ny]=='k'){
//                Check[nx][ny]=visited;
//            }
//        }
//    }
}

int main(){
    int M,N; // 9 12 행 9 열 12 -> x좌표 12 y좌표 9
    cin>>M>>N;
    
    for(int i=0;i<M;i++){
        for(int j=0;j<N;j++){
            char Char;
            cin >> Char;
            if(Char=='v' || Char=='k'){
                SheepWolf.push(make_pair(i,j));
            }
            cArr[i][j]=Char;
        }
    }
    bfs(M,N);
    cout << Sheep << " " << Wolf << endl;

//    for(int i=0;i<M;i++){
//        for(int j=0;j<N;j++){
//            cout << cArr[i][j] << " ";
//        }
//        cout << endl;
//    }
}