풀이

맵에서 울타리 '#'가 아닌 지역을 시작점으로 탐색을 해서 양과 늑대의 수를 체크한다.

이때 양의 수가 늑대의 수보다 많다면 양이 싸움에서 이기는 것이고,

양의 수가 늑대의 수보다 작거나 같다면 양이 싸움에서 지는 것으로 구현하면 된다.

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

int r, c, wolf, sheep;
char field[251][251];
bool vis[251][251];

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

void findSheepAndWolf(int x, int y)
{
	int w = 0, s = 0;
	queue<pair<int, int >> q;
	q.push({ x,y });
	vis[x][y] = true;
	while (!q.empty())
	{
		int x = q.front().first;
		int y = q.front().second;
		q.pop();

		if (field[x][y] == 'v') w++;
		if (field[x][y] == 'k') s++;

		for (int i = 0; i < 4; ++i)
		{
			int nx = x + dx[i];
			int ny = y + dy[i];
			if (nx < 0 || ny < 0 || nx >= r || ny >= c) continue;
			if (field[nx][ny] != '#' && !vis[nx][ny])
			{
				vis[nx][ny] = true;
				q.push({ nx,ny });
			}
		}
	}

	if (s > w) 
		sheep += s;
	else 
		wolf += w;
}

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

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

	for (int i = 0; i < r; ++i)
	{
		for (int j = 0; j < c; ++j)
		{
			if (field[i][j] != '#' && !vis[i][j])
			{
				findSheepAndWolf(i, j);
			}
		}
	}

	cout << sheep << ' ' << wolf << '\n';
	return 0;
}

'Algorithm' 카테고리의 다른 글

[백준 10799] 쇠막대기 (C++)  (0) 2021.04.08
[백준 1874] 스택 수열 (C++)  (0) 2021.04.08
[백준 2178] 미로 탐색  (0) 2021.04.05
[백준 2606] 바이러스  (0) 2021.04.05
[백준 16956] 늑대와 양  (0) 2021.04.05

+ Recent posts