문제 링크

설명

배열을 돌면서 이미 방문했거나(-1) 벽이거나(2) 범위를 벗어난 경우를 제외한 곳을 찾아 양과 늑대의 개수를 센 후 DFS 방식으로 위, 아래, 왼, 오른쪽으로 더 이상 탐색할 수 없을 때까지 탐사해나가면서 양과 늑대의 개수를 센 다음 양이 늑대보다 많을 경우와 적을 경우 빼는 작업을 해주었다.

코드

#define _CRT_SECURE_NO_WARNINGS

#include <iostream>
#include <vector>
#include <queue>

using namespace std;

int arr[251][251];
int totalSheep, totalWolves;
int sheep, wolves;
int r, c;
int di[] = { -1, 0, 1, 0 };
int dj[] = { 0, 1, 0, -1 };

void Search(int i, int j)
{
	if (i < 0 || j < 0 || i >= r || j >= c || arr[i][j] == -1 || arr[i][j] == 2)
		return;

	if (arr[i][j] == 3)
		sheep++;
	else if (arr[i][j] == 4)
		wolves++;

	arr[i][j] = -1;
	for (int n = 0; n < 4; n++)
		Search(i + di[n], j + dj[n]);
}

int main()
{
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);

	char item;
	cin >> r >> c;

	for (int i = 0; i < r; i++)
	{
		for (int j = 0; j < c; j++)
		{
			cin >> item;
			switch (item)
			{
			case '.':
				arr[i][j] = 1;
				break;
			case '#':
				arr[i][j] = 2;
				break;
			case 'o':
				arr[i][j] = 3;
				totalSheep++;
				break;
			case 'v':
				arr[i][j] = 4;
				totalWolves++;
			}
		}
	}

	for (int i = 0; i < r; i++)
	{
		for (int j = 0; j < c; j++)
		{
			sheep = 0; wolves = 0;
			Search(i, j);
			if (sheep > wolves)
				totalWolves -= wolves;
			else
				totalSheep -= sheep;
		}
	}

	cout << totalSheep << ' ' << totalWolves;

	return 0;
}