[C++] [BFS] 백준 3187번 : 양치기 꿍

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

3187번: 양치기 꿍

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

using namespace std;

int v = 0, k = 0;
int R, C;	//세로, 가로
int direct[4][2] = { { 0, 1 },{ 0,-1 },{ 1,0 },{ -1,0 } };
vector<vector<char>> Map;
vector<vector<int>> check;

void BFS(int i, int j) {
	int tempV = 0, tempK = 0;
	queue<pair<int, int>> Q;

	Q.push(make_pair(i, j));
	check[i][j] = 1;

	while (!Q.empty()) {
		pair<int, int> know = Q.front();
		Q.pop();

		if (Map[know.first][know.second] == 'v')
			tempV++;
		if (Map[know.first][know.second] == 'k')
			tempK++;

		for (int i = 0; i < 4; i++) {
			int r = know.first + direct[i][0];
			int c = know.second + direct[i][1];

			if (Map[r][c] != '#' && check[r][c] == 0) {
				Q.push(make_pair(r, c));
				check[r][c] = 1;
			}
		}
	}

	if (tempV >= tempK)
		tempK = 0;
	else
		tempV = 0;

	v += tempV;
	k += tempK;
}


int main(void) {
	cin >> R >> C;

	for (int i = 0; i < R; i++) {
		vector<char> temp;
		vector<int> Tcheck;
		for (int j = 0; j < C; j++) {
			char str;
			cin >> str;
			temp.push_back(str);
			Tcheck.push_back(0);
		}
		Map.push_back(temp);
		check.push_back(Tcheck);
	}

	for (int i = 0; i < Map.size(); i++) {
		for (int j = 0; j < Map[i].size(); j++) {
			if (Map[i][j] == 'v' || Map[i][j] == 'k') {
				if (check[i][j] == 0) {
					BFS(i, j);
				}
			}
		}
	}

	cout << k << ' ' << v << endl;
}