[BOJ] 3187번_양치기 꿍_DFS (C++)

[문제]

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

울타리 속에 양과 늑대가 존재한다. 양들은 평범한 양이 아니기 때문에 울타리 속에 양이 늑대보다 많으면 늑대를 전부 잡아먹는다. 그 외의 경우에는 양이 전부 잡아먹힌다. 이 때 살아남는 양과 늑대의 수를 구하는 문제이다.

[사용 알고리즘]

DFS(깊이 우선 탐색)

[풀이 핵심]

• DFS를 돌며 울타리안에 늑대와 양이 몇 마리 존재하는 지 세어주는것이 핵심이다. DFS가 끝나면 늑대와 양의 수를 비교해서 살아남은 동물의 수를 늘려준다. 모든 연산이 끝난 후 최종적으로 살아남은 양과 늑대의 수를 출력하면 된다.

[코드]

//boj3187번_양치기 꿍_그래프

#include<iostream>

using namespace std;

char graph[251][251];
bool visited[251][251];

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

int R, C;

int sheep = 0;
int wolf = 0;
int sheep_result = 0;
int wolf_result = 0;

void DFS(int x, int y) {
	visited[x][y] = true;

	if (graph[x][y] == 'v') {
		wolf++;
	}
	else if (graph[x][y] == 'k') {
		sheep++;
	}

	for (int i = 0; i < 4; i++) {
		int next_x = x + dx[i];
		int next_y = y + dy[i];

		if (next_x >= 0 && next_x < R && next_y >= 0 && next_y < C && graph[next_x][next_y] != '#' && !visited[next_x][next_y]) {
			DFS(next_x, next_y);
		}
	}
}

int main() {
	cin >> R >> C;

	for (int i = 0; i < R; i++) {
		for (int j = 0; j < C; j++) {
			cin >> graph[i][j];
		}
	}

	for (int i = 0; i < R; i++) {
		for (int j = 0; j < C; j++) {
			if ((graph[i][j] == 'v' || graph[i][j] == 'k') && !visited[i][j]) {
				wolf = 0;
				sheep = 0;

				DFS(i, j);

				if (wolf < sheep) {
					sheep_result += sheep;
				}
				else if (sheep <= wolf) {
					wolf_result += wolf;
				}
			}
		}
	}

	cout << sheep_result << " " << wolf_result;

	return 0;
}