3184_양

▶실버1

풀이

2차원 bfs문제. 울타리 안 한 영역마다 bfs를 돌려주고 그 영역 내의 양 수와 늑대 수를 세서 양 > 늑대 일 경우 양 수를 더해주고, 양 <= 늑대 일 경우 늑대 수를 더해준다. 어렵지 않은 문제였는데 bfs돌리면서 만나는 양과 늑대만 신경쓰고 처음 출발 지점이 양인지 늑대인지 신경쓰지 않아서 계속 다른 답 나왔다.

 

코드

#include <iostream>
#include <cstring>
#include <string>
#include <cmath>
#include <vector>
#include <algorithm>
#include <ctime>
#include <queue>
using namespace std;

queue <pair<int, int>> q;
int r[4] = { 1, -1, 0, 0 }; //동, 서
int c[4] = { 0, 0, 1, -1 }; //북, 남
bool visited[251][251]; //방문 여부
char garden[251][251];
int cnto, cntv; //마지막에 남은 양, 늑대 수
int tmpo, tmpv; //한 영역 내의 양, 늑대 수

void bfs(int tmpo, int tmpv) {
	while (!q.empty()) {
		int x = q.front().first;
		int y = q.front().second;
		q.pop();
		
		for (int i = 0; i < 4; i++) {
			int nx = x + r[i];
			int ny = y + c[i];
			if (visited[nx][ny] == false && garden[nx][ny] == '.') {
				visited[nx][ny] = true;
				q.push({ nx, ny });
			}
			else if (visited[nx][ny] == false && garden[nx][ny] == 'o') {
				tmpo++;
				visited[nx][ny] = true;
				q.push({ nx, ny });
			}
			else if (visited[nx][ny] == false && garden[nx][ny] == 'v') {
				tmpv++;
				visited[nx][ny] = true;
				q.push({ nx, ny });
			}
			else { continue; }
		}
	}
	if (tmpo > tmpv) {
		cnto += tmpo;
	}
	else {
		cntv += tmpv;
	}
}
int main() {
	ios::sync_with_stdio(false);
	cin.tie(NULL); cout.tie(NULL);

	int r, c;
	cin >> r >> c;
	for (int i = 0; i < r; i++) {
		for (int j = 0; j < c; j++) {
			cin >> garden[i][j];
		}
	}
	for (int i = 0; i < r; i++) {
		for (int j = 0; j < c; j++) {
			if (visited[i][j] == false && garden[i][j] != '#') {
				q.push({ i, j });
				if (garden[i][j] == 'o') {
					tmpo++;
				}
				else if(garden[i][j] == 'v') {
					tmpv++;
				}
				visited[i][j] = true;
				bfs(tmpo, tmpv);
				tmpo = 0;
				tmpv = 0;
			}
		}
	}
	cout << cnto << " " << cntv;
}