백준 3187번: 양치기 꿍 (C++)

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

3187번: 양치기 꿍

 

 

풀이

울타리 안의 양과 늑대 마리 수를 비교하는 게 중요한 문제.

 

BFS, DFS 어떤 것으로 풀어도 상관 없는데 난 BFS로 풀었다. (앞으로는 구현하기 쉬운 DFS로 풀어야지)

 

양이 있는 곳을 찾아 그 부분에서 탐색을 진행했다. 

goY[4] 와 goX[4] 배열을 만들어서 4 방향으로 뻗어나가는 방식으로 진행했고

마을을 벗어나거나 울타리인 경우, 그리고 방문한 경우는 다음 방향을 탐색했다.

 

양과 늑대인 경우, 각각 카운트 변수로 숫자를 세고 BFS를 빠져나온 경우

늑대의 수가 양의 숫자보다 많거나 같을 경우 늑대에 카운트를 더해주고 

반대의 경우는 양에 카운트를 더해주었다.

 

문자열로 입력받아 숫자로 변환시켜주었는데 오히려 읽기 어렵게 된 것 같아서 다음부터는 입력받은대로 배열에 넣어주어야겠다.

 

전체 코드

#include <iostream>
#include <algorithm>
#include <queue>
using namespace std;

int R,C;
int board[252][252] = { 0, };
int visited[252][252] = { 0, };
int goY[4] = { 0,0,1,-1 }, goX[4] = { -1,1,0,0 };
int sheep = 0, wolf = 0;
int sheep_cnt = 0, wolf_cnt = 0;

bool is_in_board(int y, int x) {
	if (y < 0 || x < 0 || y >= R || x >= C) return false;
	return true;
}

void bfs(int y, int x) {
	if (visited[y][x]) return;

	queue<pair<int, int>> q;
	q.push({ y,x });
	visited[y][x] = 1;
	if(board[y][x] == 2) wolf_cnt++;
	else sheep_cnt++;

	while (!q.empty()) {
		pair<int, int> now = q.front();

		q.pop();

		for (int i = 0; i < 4; i++) {
			pair<int, int> next = { now.first + goY[i] , now.second + goX[i] };

			if (!is_in_board(next.first , next.second)) continue;
			if (!board[next.first][next.second]) continue;
			if (visited[next.first][next.second]) continue;

			if (board[next.first][next.second] == 2) wolf_cnt++;
			else if (board[next.first][next.second] == 3) sheep_cnt++;

			visited[next.first][next.second] = 1;
			q.push({ next.first , next.second });
		}
	}
}

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

	cin >> R >> C;

	for (int i = 0; i < R; i++) {
		string s;
		cin >> s;
		for (int j = 0; j < C; j++) {
			if (s[j] == '.') board[i][j] = 1;
			else if (s[j] == 'v') board[i][j] = 2;
			else if (s[j] == 'k') board[i][j] = 3;
			else board[i][j] = 0;
		}
	}

	for (int i = 0; i < R; i++) {
		for (int j = 0; j < C; j++) {
			if (board[i][j] == 3 || board[i][j] == 2) {
				sheep_cnt = 0;
				wolf_cnt = 0;
				bfs(i, j);
				if (wolf_cnt >= sheep_cnt) wolf += wolf_cnt;
				else sheep += sheep_cnt;
			}

		}
	}
	cout << sheep << ' ' << wolf;
}