영벨롭 개발 일지

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

알고리즘 문제 풀이/BOJ

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

영벨롭 2022. 3. 9. 17:32

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

 

3187번: 양치기 꿍

입력의 첫 번째 줄에는 각각 영역의 세로와 가로의 길이를 나타내는 두 개의 정수 R, C (3 ≤ R, C ≤ 250)가 주어진다. 다음 각 R줄에는 C개의 문자가 주어지며 이들은 위에서 설명한 기호들이다.

www.acmicpc.net

 

 

 이 문제는 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;
}
반응형