(C++) - 백준(BOJ) 3184번 : 양

www.acmicpc.net/problem/3184

3184번: 양

bfs문제였습니다.

 

풀이방법

 1. 처음 양, 늑대 마리 수 세기 : 입력 받은 후 각자 마리 수를 세줍니다.

 2. 울타리가 아닌 부분에 대해 bfs실행 : 한 영역이란 울타리('#')로 둘러쌓인 부분입니다. 이 영역에 대해 늑대와 양의 수를 세줍니다. 만약 늑대가 양보다 많다면 해당 영역의 양의 수만큼 기존에 셌었던 양의 수에서 빼줍니다. 반대의 경우에는 늑대를 제거해줍니다.

 3. 답 출력

 

 

 

Code

#include <bits/stdc++.h>
using namespace std;
using pii = pair<int,int>;
int dx[4] = {0,0,-1,1};
int dy[4] = {-1,1,0,0};
char ground[251][251];
int visited[251][251];
int sheepCnt,wolfCnt,r,c;

void bfs(int i, int j){
    queue <pii> q;
    q.push({i,j});
    visited[i][j] = 1;
    int s = 0;
    int w = 0;
    if(ground[i][j] == 'o') s++;
    else if(ground[i][j] == 'v') w++;
    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 + dx[i];
            int ny = y + dy[i];
            if(0 > nx || nx >= r || 0 > ny || ny >= c) continue;
            if(visited[nx][ny] || ground[nx][ny]=='#') continue;
            visited[nx][ny] = 1;
            if(ground[nx][ny] == 'o') s++;
            if(ground[nx][ny] == 'v') w++;
            q.push({nx,ny});
        }
    }
    //if 양 수 > 늑대 수 늑대 모두 제거
    if(s > w) wolfCnt -= w;
    else sheepCnt -= s;
}

int main(){
    cin >> r >> c;
    for(int i = 0; i < r; i++) cin >> ground[i];
    for(int i = 0; i < r; i++){
        for(int j = 0; j < c; j++){
            if(ground[i][j] =='o') sheepCnt++;
            if(ground[i][j] =='v') wolfCnt++;
        }
    }

    for(int i = 0; i < r; i++){
        for(int j = 0; j < c; j++){
            if(ground[i][j]!='#' && !visited[i][j]){
                bfs(i,j);
            }
        }
    }
    
    cout << sheepCnt << ' ' << wolfCnt <<'\n';
}