3187) 양치기 꿍 (C++)

 출처 

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

3187번: 양치기 꿍

 내 풀이 

#include<iostream>
#include<queue>

using namespace std;

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

char map[251][251];
bool visited[251][251];

int N = 0, M = 0;
int result_sheep = 0, result_wolf = 0;

void BFS(int x, int y);

int main()
{
	cin >> N >> M;

	for (int i = 0; i < N; i++)
	{
		string input = "";
		cin >> input;
		for (int j = 0; j < M; j++)
		{
			map[i][j] = input[j];
			if (map[i][j] == '#') visited[i][j] = true;
		}
	}


	for (int i = 0; i < N; i++)
	{
		for (int j = 0; j < M; j++)
		{
			if (!visited[i][j])
			{
				BFS(i, j);
			}
		}
	}

	cout << result_sheep << " " << result_wolf;
}

void BFS(int x, int y)
{
	int sheep = 0;
	int wolf = 0;

	queue<pair<int, int>> q;
	q.push({ x,y });
	visited[x][y] = true;

	if (map[x][y] == 'k') sheep++;
	else if (map[x][y] == 'v') wolf++;

	while (!q.empty())
	{
		int cnt_x = q.front().first;
		int cnt_y = q.front().second;

		q.pop();

		for (int i = 0; i < 4; i++)
		{
			int nx = cnt_x + dx[i];
			int ny = cnt_y + dy[i];

			if (nx < 0 || ny < 0 || nx >= N || ny >= M) continue;

			if (map[nx][ny] == '.' && !visited[nx][ny])
			{
				visited[nx][ny] = true;
				q.push({ nx,ny });
			}
			else if (map[nx][ny] == 'k' && !visited[nx][ny])
			{
				visited[nx][ny] = true;
				q.push({ nx,ny });
				sheep++;
			}
			else if (map[nx][ny] == 'v' && !visited[nx][ny])
			{
				visited[nx][ny] = true;
				q.push({ nx,ny });
				wolf++;
			}
		}
	}

	if (wolf >= sheep) result_wolf += wolf;
	else result_sheep += sheep;
}

해설

각 울타리 안에 있는걸 방처럼 생각해서 방마다 BFS를 실행해줘서 늑대가 양보다 같거나 많으면 result_wolf에 울타리 안에 있던 늑대를 전부 더해주었고 그렇지 않으면 양을 전부 더해주는걸 반복하였다.

 느낀점 

bbbbbbbbbb