[백준 BOJ][C++]3187번 양치기 꿍 풀이: BFS/DFS

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

3187번: 양치기 꿍

 

 

 이 문제는 BFS/DFS 를 사용하여 해결할 수 있습니다. 

 

 

[풀이 과정]

 

1. R과 C, 각 영역에 대한 정보 입력

2. 영역이 'k'라면 전체 양의 수를 나타내는 k값 증가, 'v'라면 전체 늑대 수를 나타내는 v값 증가

3. 아직 방문하지 않은 울타리로 둘러쌓인 영역 탐색(bfs)

4. 탐색 과정에서 울타리로 둘러쌓인 영역 내에서의 양의 수(knum), 늑대의 수(vnum) set

5. 탐색이 끝나면 두 수를 비교해서 전체 양의수와 전체 늑대 수 reset

6. 전체 영역 탐색할 때까지, 3~5과정 반복

 

 

전체 코드입니다. 

#include<iostream>
#include <string>
#include <vector>
#include<queue>

using namespace std;

int r, c;
int v, k;
char map[250][250];
bool visit[250][250] = { false, };

int dx[4] = { 0, 0, 1, -1 };
int dy[4] = { 1, -1, 0, 0 };

void bfs(int x, int y) {
	
	int vnum = 0;
	int knum = 0;

	queue<pair<int, int>> q;

	visit[y][x] = true;
	q.push({ x, y });

	while (!q.empty()) {
		int cx = q.front().first;
		int cy = q.front().second;

		if (map[cy][cx] == 'k')
			knum++;
		else if (map[cy][cx] == 'v')
			vnum++;

		q.pop();

		for (int i = 0; i < 4; i++) {
			int tx = cx + dx[i];
			int ty = cy + dy[i];

			if (tx < 0 || tx >= c || ty < 0 || ty >= r)
				continue;
			if (visit[ty][tx] || map[ty][tx] == '#')
				continue;

			visit[ty][tx] = true;
			q.push({ tx, ty });
		}
	}

	if (vnum >= knum) {
		k -= knum;
	}
	else {
		v -= vnum;
	}

}

int main(void) {
	cin >> r >> c;

	for (int i = 0; i < r; i++) {
		for (int j = 0; j < c; j++) {
			cin >> map[i][j];

			if (map[i][j] == 'v')
				v++;
			else if (map[i][j] == 'k')
				k++;
		}
	}

	for (int i = 0; i < r; i++) {
		for (int j = 0; j < c; j++) {
			if (!visit[i][j] && map[i][j] != '#') {
				bfs(j, i);
			}
		}
	}

	cout << k << " " << v;

	return 0;
}