코드 복사/붙여넣기 하는 당신이 아름답습니다.

1012 : 유기농 배추

풀이

DFS를 돌리자.

코드

#include <stdio.h>
#include <memory.h>

const int dx[] = { 0,0,-1,1 };
const int dy[] = { -1,1,0,0 };

int tc, n, m, k, i, j, x, y, ans;
bool farm[52][52];

void dfs(int x, int y) {
	farm[x][y] = 0;
	for (int i = 0; i < 4; i++)
		if (farm[x + dx[i]][y + dy[i]]) dfs(x + dx[i], y + dy[i]);
}

int main() {
	scanf("%d", &tc);

	while (tc--) {
		ans = 0, memset(farm, 0, sizeof(farm));
		scanf("%d %d %d", &n, &m, &k);
		while (k--) {
			scanf("%d %d", &x, &y);
			farm[++x][++y] = 1;
		}
		for (i = 1; i <= n; i++)
			for (j = 1; j <= m; j++)
				if (farm[i][j]) ans++, dfs(i, j);
		printf("%d\n", ans);
	}

	return 0;
}

아무말

백준, 백준 온라인 저지, BOJ, Baekjoon Online Judge, C, C++, 씨, 씨쁠쁠, JAVA, algorithm, 자바, 알고리즘, 자료구조, 문제, 문제 풀이, 풀이

wookje.kwon's profile image

wookje.kwon

2017-03-13 11:41

Read more posts by this author