백준 3184 양

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

문제와 채점은 위 사이트에서 확인 하실 수 있습니다

 

이 문제는 마당에 양과 늑대가 있는데 양이 더많다면 양이 늑대를 모두 해치우고 그렇지 않다면 늑대가 모두 양을 해치울때 최종적으로 남는 양과 늑대의 수를 출력하는 문제입니다. 

 

우선 마당이 형성되기 위해서는 사방이 울타리로 둘러 쌓여 있어야 하므로 저는 dfs를 통해 하나의 마당영역을 탐색하며 늑대와 양의 수를 찾아 내었습니다. dfs가 끝난뒤 조건에따라 양이 많으면 양을 +해주고 그렇지 않으면 늑대를 + 해준뒤 또다른 영역이 있는지 탐색하는식으로 모든 영역을 탐색하는 방법으로 문제를 해결하였습니다.

 

다음은 코드입니다.

 

#include <iostream>
#include <string>

using namespace std;

char yard[251][251];
int visited[251][251];
int nextx[4] = {1, 0, -1, 0};
int nexty[4] = {0, 1, 0, -1};
int R,C;
int resultwolf, resultsheep;
int wolf,sheep;

void dfs(int a, int b) {
	
	visited[a][b] = 1;
	if(yard[a][b] == 'v')
			wolf++;
	else if(yard[a][b] == 'o')
			sheep++;
				
	for(int i = 0; i < 4; i++) {
		int x = a + nextx[i];
		int y = b + nexty[i];
		
		if(x < 0 || x >= R || y < 0 || y >= C)
			continue;
		
		if(!visited[x][y]) {
			dfs(x, y);
		}
	}
}

int main(void) {
	ios_base::sync_with_stdio(false); cin.tie(NULL);
	cin >> R >> C;
	
	for(int i = 0; i < R; i++) {
		string str;
		cin >> str;
		for(int j = 0; j < C; j++) {
			yard[i][j] = str[j];
			if(str[j] == '#')
				visited[i][j] = 1;
		}
	}
	
	for(int i = 0; i < R; i++)
		for(int j = 0; j < C; j++) {
			if(!visited[i][j]) {
				wolf = 0;
				sheep = 0;
				dfs(i, j);
				if(wolf >= sheep) 
					resultwolf += wolf;
				else
					resultsheep += sheep;
			}
		}
	
	cout<<resultsheep<<' '<<resultwolf;
	return 0;	
}