백준3184 - 양

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

3184번: 양

간단한 dfs문제다. 울타리(#)를 만나거나 이미 방문햇던 곳은 dfs를 수행하지 않는다. 땅(.), 양(o), 늑대(v)인 곳을 방문하고 양을 만날 때는 양의 갯수를 세주고 늑대를 만날 때는 늑대의 갯수를 세준다. 같은 구역 내에 늑대가 양보다 같거나 많으면 양의 갯수를 0으로 초기화하고 양이 늑대보다 많다면 늑대의 갯수를 0으로 초기화한다. 최종적으로 살아남는 양이 수와 살아남는 늑대의 수를 출력한다.

 

#include <iostream>
using namespace std;

int R, C; //R x X개의 땅이 존재
bool check[251][251]; //방문여부
char mat[251][251]; //땅의 정보

//동서남북으로 한 칸 이동
int dx[] = { 1,-1,0,0 }; 
int dy[] = { 0,0,1,-1 };

int vcnt, vres; //구역당 늑대의 수, 최종 늑대의 수
int ocnt, ores; //구역당 양의 수, 최종 양의 수

//dfs수행
void dfs(int x, int y) {
	if (mat[x][y] == '#' || check[x][y]) { //이미 방문했던 곳이나 울타리면
		return; //dfs종료
	}
	check[x][y] = true; //현재 위치 방문처리
	if (mat[x][y] == 'v') { //현재 위치가 늑대이면
		vcnt++; //늑대 증가
	}
	else if (mat[x][y] == 'o') { //현재 위치가 양이면
		ocnt++; //양 증가
	}
	for (int i = 0; i < 4; i++) { //동서남북으로 한 칸 이동
		int nx = x + dx[i];
		int ny = y + dy[i];
		if (1 <= nx && nx <= R && 1 <= ny && ny <= C && !check[nx][ny]) { //현재 이동한 위치가 땅의 범위 안이고 방문하지 않은 곳이면
			dfs(nx, ny); //dfs수행
		}
	}
}

int main() {
	//땅의 정보 입력
	cin >> R >> C;
	for (int i = 1; i <= R; i++) {
		for (int j = 1; j <= C; j++) {
			cin >> mat[i][j];
		}
	}

	for (int i = 1; i <= R; i++) {
		for (int j = 1; j <= C; j++) {
			dfs(i, j); //현재 위치에서 dfs실행
			if (vcnt == 0 && ocnt == 0) { //dfs결과 아무런 양과 늑대도 발견하지 못했으면
				continue; //반복문으로 다시 올라감
			}
			if (vcnt >= ocnt) { //늑대의 수가 양의 수 이상이면
				ocnt = 0;
			}
			else { //양이 늑대보다 많다면
				vcnt = 0;
			}

			//양의 결과와 늑대의 결과 수정
			vres = vres + vcnt;
			ores = ores + ocnt;

			//영역 안에 있는 양의 수와 늑대의 수를 0으로 초기화
			vcnt = 0; 
			ocnt = 0;
		}
	}

	cout << ores << ' ' << vres;
}