[C++] 1012번 (유기농 배추)

아마도 가장 전형적인 DFS 문제가 아닐까 싶다.

한 지점에 지렁이가 있으면 그와 이웃한 곳에는 지렁이가 없어도 된다 (대각선 제외) .

모든 땅을 전부 돌면서 배추가 없는 곳과 방문을 했던 곳은 볼 필요 없고

배추가 있으면서 동시에 방문 하지 않았던 곳에서 출력값을 ++ 해준다.

그리고 DFS 함수를 이용해 그와 이웃한 곳에 있는 땅을 전부 방문해서 그곳에 배추가 있으면 방문기록을 해준다.

#include <iostream>
using namespace std;

int farm[50][50];
int visited[50][50];
int m, n, k;

void DFS(int a, int b) {

	if (farm[a + 1][b] && a + 1 < m && !visited[a + 1][b]) {
		visited[a + 1][b] = 1;
		DFS(a + 1, b);
	}
	if (farm[a - 1][b] && a - 1 >= 0 && !visited[a - 1][b]) {
		visited[a - 1][b] = 1;
		DFS(a - 1, b);
	}
	if (farm[a][b + 1] && b + 1 < n && !visited[a][b + 1]) {
		visited[a][b + 1] = 1;
		DFS(a, b + 1);
	}
	if (farm[a][b - 1] && b - 1 >= 0 && !visited[a][b - 1]) {
		visited[a][b - 1] = 1;
		DFS(a, b - 1);
	}

}

int main() {
	int t; cin >> t;
	int x, y;

	while (t--) {

		for (int i = 0; i < 50; i++) {
			for (int j = 0; j < 50; j++) {
				farm[i][j] = 0;
				visited[i][j] = 0;
			}
		}

		cin >> m >> n >> k;		

		for (int i = 0; i < k; i++) {
			cin >> x >> y;
			farm[x][y] = 1;
		}

		int result = 0;

		for (int i = 0; i < m; i++) {
			for (int j = 0; j < n; j++) {
				if (farm[i][j] && !visited[i][j]) {
					result++;
					visited[i][j] = 1;
					DFS(i, j);
				}
			}
		}

		cout << result << "\n";
	}
}