[C/C++ 백준 1012번] 유기농 배추 (Silver 2)

www.acmicpc.net/problem/1012

1012번: 유기농 배추

배추를 만나면, 해당 배추에서부터 dfs를 진행한다. 그리고 새로 배추를 만날때마다 ans++를 해주면서 모든 칸에 대해 세어준다.

 

#include <cstdio>
int array[51][51];
bool visit[51][51];
void dfs(int x, int y){
	visit[x][y] = true;
	if(array[x+1][y] == 1 && visit[x+1][y]==false)
		dfs(x+1, y);
	if(array[x][y+1] == 1 && visit[x][y+1]==false)
		dfs(x, y+1);
	if(array[x-1][y] == 1 && visit[x-1][y]==false)
		dfs(x-1, y);
	if(array[x][y-1] == 1 && visit[x][y-1]==false)
		dfs(x, y-1);
}
int main(void){
	int T;
	scanf("%d", &T);
	for(int i=0; i<T; i++){
		for(int q=0; q<51; q++){
			for(int w=0; w<51; w++){
				array[q][w]=0;
				visit[q][w]=false;
			}
		}
		int M, N, K, a, b, ans = 0;
		scanf("%d %d %d", &M, &N, &K);
		for(int j=0; j<K; j++){
			scanf("%d %d", &a, &b);
			array[a][b]=1;
		}
		for(int q=0; q<51; q++){
			for(int w=0; w<51; w++){
				if(array[q][w]==1 && visit[q][w]==false){
					dfs(q, w);
					ans++;
				}
			}
		}
		printf("%d\n", ans);
	}
}