[백준][C++] 3184: 양

문제 링크: https://www.acmicpc.net/problem/3184

 

bfs 또는 dfs로 각 영역마다 양의 수, 늑대의 수를 세서 양이 많으면 양의 수를 누적, 아니면 늑대의 수를 누적해서 마지막에 출력하면 됩니다

#include <bits/stdc++.h>
using namespace std;


const int dy[] = { -1, 0, 1, 0 };
const int dx[] = { 0, 1, 0, -1 };

int r, c;
char board[250][250];
bool visited[250][250];


constexpr bool in_range(int y, int x) {
	return y >= 0 && y < r&& x >= 0 && x < c;
}

void dfs(int y, int x, int& sheep, int& wolves) {
	visited[y][x] = true;

	if (board[y][x] == 'o') ++sheep;
	else if (board[y][x] == 'v') ++wolves;

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

		if (in_range(ny, nx) && board[ny][nx] != '#' && !visited[ny][nx])
			dfs(ny, nx, sheep, wolves);
	}
}

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

	cin >> r >> c;
	for (int i = 0; i < r; ++i)
		for (int j = 0; j < c; ++j)
			cin >> board[i][j];

	int sheep_counter = 0, wolves_counter = 0;
	
	for (int i=0; i<r; ++i)
		for (int j = 0; j < c; ++j) {
			int s=0, w=0;
			if (!visited[i][j])
				dfs(i, j, s, w);

			if (s > w) sheep_counter += s;
			else wolves_counter += w;
		}

	cout << sheep_counter << ' ' << wolves_counter << '\n';
	
	return 0;
}

dfs로 짰습니다

bfs로 짜는게 메모리 덜 먹을 것 같네요