BOJ_3148 : 양

문제

미키의 뒷마당에는 특정 수의 양이 있다. 그가 푹 잠든 사이에 배고픈 늑대는 마당에 들어와 양을 공격했다.

마당은 행과 열로 이루어진 직사각형 모양이다. 글자 ‘.’ (점)은 빈 필드를 의미하며, 글자 ‘#’는 울타리를, ‘o’는 양, ‘v’는 늑대를 의미한다.

한 칸에서 수평, 수직만으로 이동하며 울타리를 지나지 않고 다른 칸으로 이동할 수 있다면, 두 칸은 같은 영역 안에 속해 있다고 한다. 마당에서 “탈출”할 수 있는 칸은 어떤 영역에도 속하지 않는다고 간주한다.

다행히 우리의 양은 늑대에게 싸움을 걸 수 있고 영역 안의 양의 수가 늑대의 수보다 많다면 이기게 된다. 그렇지 않다면 늑대가 그 지역 안의 모든 양을 먹는다.

맨 처음 모든 양과 늑대는 마당 안 영역에 존재한다.

아침이 도달했을 때 살아남은 양과 늑대의 수를 출력하는 프로그램을 작성하라.

입력

첫 줄에는 두 정수 R과 C가 주어지며(3 ≤ R, C ≤ 250), 각 수는 마당의 행과 열의 수를 의미한다.

다음 R개의 줄은 C개의 글자를 가진다. 이들은 마당의 구조(울타리, 양, 늑대의 위치)를 의미한다.

출력

하나의 줄에 아침까지 살아있는 양과 늑대의 수를 의미하는 두 정수를 출력한다.

C++ 코드

#include <iostream>
#include <algorithm>
#include <vector>
#include <queue>
#include <tuple>

using namespace std;
int n, m;
int dx[] = { 1,-1, 0,0 };
int dy[] = { 0,0, -1,1 };
vector<string > s(250);
int o_ans = 0;
int w_ans = 0;

void bfs(vector< vector<int> >& com ,int x, int y, int index) {
	queue< pair<int, int> > q;
	com[x][y] = index;
	q.push(make_pair(x, y));
	int wolf = 0;
	int sheep = 0;

	while (!q.empty()) {
		int x_now, y_now;
		tie(x_now, y_now) = q.front();
		q.pop();
		if (s[x_now][y_now] == 'o') sheep++;
		else if (s[x_now][y_now] == 'v') wolf++;

		for (int k = 0; k < 4; k++) {
			int nx = x_now + dx[k];
			int ny = y_now + dy[k];

			if (nx < 0 || nx >= n || ny < 0 || ny >= m) continue;
			if (com[nx][ny] != -1 || s[nx][ny] == '#') continue;

			q.push(make_pair(nx, ny));
			com[nx][ny] = index;
			
		}

	}
	if (wolf < sheep) {
		o_ans += sheep;
	}
	else if( wolf >= sheep){
		w_ans += wolf;
	}
}


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

	cin >> n >> m;
	for (int i = 0; i < n; i++) {
		cin >> s[i];
	}

	vector< vector<int> > com(n, vector<int>(m, -1));
	int index = 1;
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < m; j++) {
			if (com[i][j] != -1 || s[i][j] == '#') continue;
			bfs(com, i, j, index);
			index++;
		}
	}
	cout << o_ans << ' ' << w_ans << '\n';

	return 0;
}