[백준/C++] 3184 양

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

 

코드

#include <iostream>
#include <queue>
using namespace std;

#define MAX 251
#define FASTIO ios::sync_with_stdio(false); cin.tie(NULL);
typedef pair<int, int> pi;
int r, c, dx[4] = { 1,-1,0,0 }, dy[4] = { 0, 0,1,-1 };
int fs, fw;

string arr[MAX];
bool visit[MAX][MAX];

void bfs(int i, int j) {
	visit[i][j] = true;
	int ansS = 0, ansW = 0;

	queue<pi> q;
	q.push({ i, j });
	while (!q.empty()) {
		int x = q.front().first;
		int y = q.front().second;
		q.pop();

		if (arr[x][y] == 'o') ansS++;
		if (arr[x][y] == 'v') ansW++;

		for (int i = 0, gx, gy; i < 4; i++) {
			gx = x + dx[i];
			gy = y + dy[i];

			if (gx >= 0 && gx < r && gy >= 0 && gy < c && !visit[gx][gy]) {
				if (arr[gx][gy] == '#') continue;
				visit[gx][gy] = true;
				q.push({ gx, gy });
			}
		}
	}

	if (ansS > ansW) fs += ansS;
	else fw += ansW;
}

int main() {
	FASTIO;

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

	for (int i = 0; i < r; i++)
		for (int j = 0; j < c; j++)
			if (!visit[i][j]) 
				bfs(i, j);

	cout << fs << " " << fw << "\n";
	return 0;
}

 

설명

마당 정보를 입력 받고 반복문을 돌면서 방문하지 않은 칸에 대해서 영역을 계산합니다. bfs 함수를 이용해서 양과 늑대의 수를 세고, 양이 늑대보다 많을 때는 최종 양의 수에 현재 영역 안에서의 양의 수를 더합니다. 그렇지 않은 경우에는 최종 늑대의 수에 현재 영역에서의 늑대의 수를 더해줍니다.

 

모든 영역에 대한 확인을  한 후 최종 양의 수, 늑대의 수를 출력합니다.

 

느낀 점

단순 bfs를 구현합니다.