BaekJoon 3184번: 양(C++)

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

3184번: 양

풀이법

1) BFS나 DFS 알고리즘을 활용하여, 빈 공간이 있거나, 양이 있거나, 늑대가 있는 칸들과 연결된 칸들을 반복하며 탐색하면 되는 문제이다.

2) 한 공간 내에 양이 더 많은 경우 늑대를 쫓아내고, 늑대의 수가 양과 같거나 많으면 양이 없어지는 것을 감안하여, 한 공간 내에서 양의 수와 늑대의 수를 구한 후 조건을 활용하여 코딩을 진행하였다.

#include <string>
#include <iostream>
#include <vector>
#include <algorithm>
#include <math.h>
#include <map>
#include <queue>
#include <cstring>
#define INF 987654321
using namespace std;

int r, c;
char arr[251][251];
bool visited[251][251];
int vx[4] = { 1,0,0,-1 };
int vy[4] = { 0,1,-1,0 };
int totalSheep = 0;
int totalWolf = 0;
void bfs(int a, int b)
{
	queue<pair<int, int>> q;
	visited[a][b] = true;
	q.push({ a,b });
	int sheep = 0;
	int wolf = 0;
	while (!q.empty())
	{
		int nowX = q.front().first;
		int nowY = q.front().second;
		q.pop();

		if (arr[nowX][nowY] == 'o')
			sheep++;
		else if (arr[nowX][nowY] == 'v')
			wolf++;

		for (int i = 0; i < 4; i++)
		{
			int nextX = nowX + vx[i];
			int nextY = nowY + vy[i];
			if (nextX < 0 || nextY < 0 || nextX >= r || nextY >= c)
				continue;
			if (arr[nextX][nextY] == '.' || arr[nextX][nextY] == 'o' || arr[nextX][nextY] == 'v')
			{
				if (!visited[nextX][nextY])
				{
					visited[nextX][nextY] = true;
					q.push({ nextX,nextY });
				}
			}
		}
	}
	if (sheep > wolf)
		totalSheep += sheep;
	else
		totalWolf += wolf;
}

int main()
{
	cin.tie(0);
	ios::sync_with_stdio(false);
	cin >> r >> c;
	for (int i = 0; i < r; i++)
	{
		for (int j = 0; j < c; j++)
		{
			cin >> arr[i][j];
		}
	}
	for (int i = 0; i < r; i++)
	{
		for (int j = 0; j < c; j++)
		{
			if (arr[i][j] == '.' || arr[i][j] == 'o' || arr[i][j] == 'v')
			{
				if (!visited[i][j])
				{
					bfs(i, j);
				}
			}
		}
	}
	cout << totalSheep << " " << totalWolf;
}