[백준/BOJ] 백준 3187번 : 양치기 꿍

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

3187번: 양치기 꿍

어떤 영역을 발견하면 그 영역을 dfs 해 그 영역의 양의 수와 늑대의 수를 구하고, 그 영역의 양의 수와 늑대의 수가 어떻게 될지 구해 전체 영역의 양의 수와 늑대의 수가 어떻게 될지 구한다

 

코드

#include <iostream>
#include <algorithm>
#include <vector>
#include <utility>
#include <cstring>
#include <string>
using namespace std;

vector<string> board;
int visited[250][250];
int r, c;
int dx_dy[4][2] = { {0,-1},{-1,0},{0,1},{1,0} };
int total_sheep = 0;
int total_wolf = 0;
int temp_sheep, temp_wolf;

//here위치에서 해당영역을 dfs한다
void numCheck(pair<int, int> here)
{
	visited[here.first][here.second] = 1;

	//양일때
	if (board[here.first][here.second] == 'k')
		temp_sheep++;

	//늑대일때
	else if (board[here.first][here.second] == 'v')
		temp_wolf++;


	for (int i = 0; i < 4; i++)
	{
		pair<int, int> there = make_pair(here.first + dx_dy[i][0], here.second + dx_dy[i][1]);

		if (there.first >= 0 && there.first < r && there.second >= 0 && there.second < c && board[there.first][there.second] != '#' && visited[there.first][there.second] == 0)
		{
			numCheck(there);
		}
	}
}

void Solve()
{
	memset(visited, 0, sizeof(visited));

	for (int i = 0; i < r; i++)
		for (int j = 0; j < c; j++)
		{
			//한 영역을 발견 했을때
			if (board[i][j] != '#' && visited[i][j] == 0)
			{
				temp_sheep = 0;
				temp_wolf = 0;

				//그 영역을 깊이우선 탐색해 해당영역의 양과 늑대의 수를 구한다
				numCheck(make_pair(i, j));

				//양의 수가 많을때
				if (temp_sheep > temp_wolf)
					total_sheep += temp_sheep;

				else
					total_wolf += temp_wolf;
			}

		}
}

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

	string temp;

	cin >> r >> c;

	for (int i = 0; i < r; i++)
	{
		cin >> temp;
		board.push_back(temp);
	}

	Solve();

	cout << total_sheep << " " << total_wolf;

	return 0;
}