양

#include<iostream>
#include<cstdio>
#include<utility>
#include<queue>

using namespace std;

int r, c;
int map[250][250];
bool d[250][250];
int dx[] = { 0,0,1,-1 };
int dy[] = { 1,-1,0,0 };
int wolf;
int lambs;

void bfs(int x, int y) {
	queue<pair<int, int>> q;
	q.push({ x,y });
	d[x][y] = true;
	int wolv = 0; int lamb = 0;
	if (map[x][y] == 2)
		wolv++;
	if (map[x][y] == 1)
		lamb++;
	while (!q.empty()) {
		x = q.front().first; 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) {
				if (map[nx][ny] != 3 && d[nx][ny] == false) {
					d[nx][ny] = true;
					if (map[nx][ny] == 2)
						wolv++;
					if (map[nx][ny] == 1)
						lamb++;
					q.push({ nx,ny });
				}
			}
		}
	}
	if (wolv < lamb) lambs += lamb;
	else wolf += wolv;
}

int main() {
	std::ios::sync_with_stdio(false);
	cin >> r >> c;
	for (int i = 0; i < r; i++) {
		for (int j = 0; j < c; j++) {
			char x;
			cin >> x;
			if (x == '.') {
				map[i][j] = 0;
			}
			if (x == 'o') {
				map[i][j] = 1;
			}
			if (x == 'v') map[i][j] = 2;
			if (x == '#')map[i][j] = 3;
		}
	}
	for (int i = 0; i < r; i++) {
		for (int j = 0; j < c; j++) {
			if (map[i][j] != 3 && d[i][j] == false) {
				bfs(i, j);
			}
		}
	}
	cout << lambs << " " << wolf << '\n';
    return 0;
}

 

너무너무너무 쉬운 BFS문제 푸는데 20분정도 걸린거같다.

울타리가 아닌 곧에서 BFS하고, 그안에서 늑대와 양비교해서 BFS 끝날때 비교후, 전역변수에 더해주고를 반복하면, 문제가 쉽게풀린다.