백준 3184 양 (C++)

3184번: 양

bfs를 이용한 문제이다. 기존 다른 bfs 문제와 로직이 유사하게 흘러간다. 반복문을 돌면서 울타리가 아닐 때, 방문한 적이 없는 좌표일 경우 bfs를 돌아준다. bfs를 돌면서 o나 v를 만날 경우 이를 카운트 해주고 두 개수를 비교해 sheep과 wolf에 저장해주었다. 어렵지 않게 풀 수 있었던 문제였다.

#include <iostream>
#include <queue>

using namespace std;

int R, C;
char A[250][250];
int dy[4] = { -1,1,0,0 };
int dx[4] = { 0,0,-1,1 };
bool check[250][250];
int sheep = 0, wolf = 0;

void bfs(int a, int b) {
    queue<pair<int, int>> q;
    int ts = 0, tw = 0;

    q.push({ a,b });
    check[a][b] = true;

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

        q.pop();

        if (A[y][x] == 'o') ts++;
        if (A[y][x] == 'v') tw++;

        for (int i = 0; i < 4; i++) {
            int ny = y + dy[i];
            int nx = x + dx[i];

            if (ny < 0 || nx < 0 || ny >= R || nx >= C) continue;
            if (A[ny][nx] == '#') continue;
            if (check[ny][nx]) continue;

            q.push({ ny,nx });
            check[ny][nx] = true;
        }
    }

    sheep = ts > tw ? sheep + ts : sheep;
    wolf = tw >= ts ? wolf + tw : wolf;
}

void solution() {
    for (int i = 0; i < R; i++) {
        for (int j = 0; j < C; j++) {
            if (A[i][j] != '#' && !check[i][j]) {
                bfs(i, j);
            }
        }
    }

    cout << sheep << " " << wolf;
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL); cout.tie(NULL);

    cin >> R >> C;

    for (int i = 0; i < R; i++) {
        for (int j = 0; j < C; j++) {
            cin >> A[i][j];
        }
    }

    solution();

    return 0;
}