3184번: 양 (백준 온라인 저지, C++)

문제 해설

 

 simulate 함수를 만들어, 같은 울타리 내에 있는 양과 늑대의 수 중 늑대의 수가 양의 수 이상인 경우 양의 수를 0으로 바꾼 후 리턴해주고, 양의 수가 늑대의 수보다 많을 경우 늑대의 수를 0으로 만들어 리턴해 주었습니다. 단순한 bfs 알고리즘을 통해 문제를 풀 수 있습니다.

 

 

코드

 

#include <iostream>
#include <string>
#include <queue>
using namespace std;
 
int r, c;
string a[250];
bool isVisit[250][250];
int dx[] = { 0, 0, -1, 1 };
int dy[] = { -1, 1, 0, 0 };
 
pair<int, int> simulate(int i, int j) {
 
    int s = 0, w = 0;
    queue<pair<int,int>> q;
    if (a[i][j] == 'o') s++;
    if (a[i][j] == 'v') w++;
    isVisit[i][j] = true;
    q.emplace(i, j);
    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 (nx < 0 || nx >= r || ny < 0 || ny >= c || isVisit[nx][ny] == true|| a[nx][ny] == '#') continue;
 
            isVisit[nx][ny] = true;
 
            if (a[nx][ny] == 'o') s++;
            if (a[nx][ny] == 'v') w++;
 
            q.emplace(nx, ny);
        }
    }
 
    if (s > w) w = 0;
    else s = 0;
 
    return make_pair(s, w);
}
 
int main() {
 
    cin >> r >> c;
    memset(isVisit, false, sizeof(isVisit));
 
    for (int i = 0; i < r; i++) {
        cin >> a[i];
    }
    
    int sheep = 0, wolf = 0;
    for (int i = 0; i < r; i++) {
        for (int j = 0; j < c; j++) {
            
            if (isVisit[i][j] == true) continue;
 
            if (a[i][j] == 'o' || a[i][j] == 'v') {
                auto n = simulate(i, j);
                sheep += n.first;
                wolf += n.second;
            }
        }
    }
    cout << sheep << ' ' << wolf << '\n';
 
    return 0;
}

 

 

 

제출 결과

 

 

 

문제 출처

 

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

3184번: 양