BOJ (C/C++) 3184번: 양

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

3184번: 양

---

풀이

입력 받을 때 양과 늑대의 총 갯수를 세고, 탐색 가능한 지점을 저장했다. 이 지점들을 BFS로 탐색하며 각 조건에 맞게 제거했다.처음엔 '.'인 지점만 저장했는데, 그럴 경우 양과 늑대만 있는 지역은 계산되지 않아 '#'이 아닌 모든 지점을 저장했다.

---

코드

#include <stdio.h>
#include <vector>
#include <queue>
using namespace std;

int ground[251][251];
int sheep, wolf;
bool visited[251][251];
vector <pair<int, int>> V;

auto Morning(int R, int C) {
	int d[4][2] = { {-1,0},{1,0},{0,-1},{0,1} };
	int x, y, nx, ny, sh, wo;
	queue <pair<int, int>> Q;

	for (int v = 0; v < V.size(); v++) {
		x = V[v].first, y = V[v].second;
		if (visited[x][y]) continue;

		//init
		sh = wo = 0;
		Q.push({ x,y });
		visited[x][y] = true;

		// 시작하는 칸이 양/늑대인 경우
		if (ground[x][y] == 2) wo++;
		else if (ground[x][y] == 3) sh++;

		// BFS
		while (!Q.empty()) {
			x = Q.front().first, y = Q.front().second;
			Q.pop();
			for (int i = 0; i < 4; i++) {
				nx = x + d[i][0], ny = y + d[i][1];

				if (visited[nx][ny] || !ground[nx][ny] || nx < 0 || nx >= R || ny < 0 || ny >= C) continue;

				visited[nx][ny] = true;
				Q.push({ nx,ny });

				// 탐색하는 지역 내의 양, 늑대 수 구하기
				if (ground[nx][ny] == 2) wo++;
				else if (ground[nx][ny] == 3) sh++;
			}
		}

		// 양, 늑대 수 비교 후 제거
		if (sh > wo) wolf -= wo;
		else sheep -= sh;
	}
	printf("%d %d", sheep, wolf);
}

int main() {
	int R, C;
	char s[251];

	scanf("%d %d\n", &R, &C);

	// sheep = wolf = 0;
	for (int i = 0; i < R; i++) {
		scanf("%s", s);
		for (int j = 0; j < C; j++) {

			// 탐색 가능한 모든 지역 저장
			if (s[j] != '#') V.push_back({ i,j });

			if (s[j] == '.') ground[i][j] = 1;
			else if (s[j] == 'v') {
				ground[i][j] = 2; // 늑대
				wolf++;
			}
			else if (s[j] == 'o') {
				ground[i][j] = 3; // 양
				sheep++;
			}
		}
	}

	Morning(R, C);
}