백준 1012 유기농 배추

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

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

 

이 문제는 배추밭에 배추가 심어져있는 좌표를 입력받은뒤 배추가 심어진 부분의 영역의 수를 구하는 문제입니다. 서로 인접해있는 영역은 하나의 배추벌레로 모두 보호가 되므로 main함수에서 dfs를 호출하는 횟수가 곧 필요한 배추벌레의 숫자입니다. 특별함은 없는 문제입니다.

 

다음은 코드입니다.

 

 #include <iostream>

using namespace std;

int cabbage[51][51];
int nextx[4] = {1, 0, -1, 0};
int nexty[4] = {0, 1, 0, -1};
int M,N; 

void dfs(int a, int b) {
	cabbage[a][b] = 0;
	
	for(int i = 0; i < 4; i++) {
		int x = a + nextx[i];
		int y = b + nexty[i];
		if(x < 0 || x >= N || y < 0 || y >= M)
			continue;
		
		if(cabbage[x][y])
			dfs(x, y);
	}
		
}

int main(void) {
	ios_base::sync_with_stdio(false); cin.tie(NULL);
	int T,K;
	int worm;
	cin >> T;
	while(T--) {
		worm = 0;
		cin >> M >> N >> K;
		int x,y;
		while(K--) {
		cin >> y >> x;
		cabbage[x][y] = 1;
		}
		for(int i = 0; i < N; i++)
			for(int j = 0; j < M; j++) {
				if(cabbage[i][j]) {
					dfs(i, j);
					worm++;
				}
	
		}	
	cout<<worm<<'\n';
	}
	return 0;
}