[백준 1012] 유기농 배추

# 문제링크

www.acmicpc.net/problem/1012

1012번: 유기농 배추

 

섬 개수 세는 문제랑 비슷한 문제다. DFS로 같은 섬의 방문한 map을 다시 0으로 변경시켜주어 다시 세지 않도록 한다. 모든 1을 0으로 바꿔주었기 때문에 여러 번 반복하더라도 초기화 할 필요가 없어서 좋다.

 

 

# 제출 코드 

# include <cstdio>

char map[50+2][50+2];
int T, M, N, K;
int yd[] = { 1, -1, 0,0 };
int xd[] = { 0, 0, 1, -1 };
void Input() {
	scanf("%d %d %d", &M, &N, &K);
	int x, y;
	for (int i = 0; i < K; i++) {
		scanf("%d %d", &x, &y);
		map[y][x] = '1';
	}
}
void DFS(int y, int x) {
	if (map[y][x] != '1') return;
	map[y][x] = '0';
	for (int i = 0; i < 4; i++) {
		int ny = y + yd[i];
		int nx = x + xd[i];
		if (nx < 0 || nx > M || ny < 0 || ny > N)continue;
		if (map[ny][nx] == '1')
			DFS(ny, nx);
	}
}
void Solve() {
	int ans = 0;
	for (int i = 0; i < N; i++) {
		for (int j = 0; j < M; j++) {
			if (map[i][j] == '1') {
				ans++;
				DFS(i,j);
			}
		}
	}
	printf("%d\n", ans);
}
int main() {
	scanf("%d", &T); // 테스트 케이스 개수
	while (T--) {
		Input();
		Solve();
	}
	return 0;
}