백준 3184번 - 양 c++

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

3184번: 양

뒷마당에 울타리에 양을 키우고 있는데 이때 살아남는 양과 늑대의 수를 구하는 알고리즘 문제이다.

문제에 입력을 받는 요소는 필드 = '.' , 울타리 = '#' , 양 = 'o', 늑대 = 'v' 로 구성된다.

이때 울타리로 둘러쌓인 영역을 하나의 영역으로 간주하며, 하나의 영역에서는 늑대가 수가 많거나 같을경우에

양은 모두 죽고 늑대는 전부 살아남으며, 예외로 양이 숫자가 더 많은경우에는 늑대만 죽고 양은 모두 살아남는다.

 

이 문제는 BFS알고리즘 이용해야 하는문제로 기존에 풀었던 문제와는 다르게 input이 문자형이라는점이 차이가 있다.

 

#include <iostream>
#include <cstdio>
#include <stack>
#include <queue>
#include <utility>
#include <cstdlib>
#include <algorithm>
#include <vector>
#include <cstring>

using namespace std;

char map[250][250];
bool visited[250][250];
int row, col;
int sh1, wo1, sh2, wo2;
int dx[4] = { -1, 1, 0, 0 };
int dy[4] = { 0, 0, -1, 1 };
bool inside(int x, int y)
{
	return (x >= 0 && x < row) && (y >= 0 && y < col);
}

void bfs(int x, int y)
{
	
	queue<pair<int, int>> q;
	q.push(make_pair(x, y));
	visited[x][y] = true;
	wo1 = 0, sh1 = 0;
	while (!q.empty()) {
		int qx = q.front().first;
		int qy = q.front().second;
		if (map[qx][qy] == 'v')
			wo1++;
		if (map[qx][qy] == 'o')
			sh1++;
		q.pop();
		for (int i = 0; i < 4; ++i) {
			int nx = qx + dx[i];
			int ny = qy + dy[i];
			if ((inside(nx, ny) == true) && (visited[nx][ny] == false) && (map[nx][ny] != '#')) {
				q.push(make_pair(nx, ny));
				visited[nx][ny] = true;
			}
		}
	}
	if (sh1 > wo1) sh2 += sh1;
	else wo2 += wo1;
}

int main(void) {
	cin >> row >> col;
	char input;
	for (int i = 0; i < row; ++i) {
		for (int j = 0; j < col; ++j) {
			cin >> input;
			map[i][j] = input;
		}
	}

	for (int i = 0; i < row; ++i) {
		for (int j = 0; j < col; ++j) {
			if ((inside(i, j) == true) && (visited[i][j] == false) && (map[i][j] != '#')) 
				bfs(i, j);
		}
	}
	cout << sh2 << " " << wo2 << endl;

	return 0;
}