(백준 1012번 유기농배추 C++) 라이님 블로그 대회 알고리즘 따라잡기 8) DFS 2

미친 디버깅 끝에 겨우 찾았다. ㅎㅎ 영타 연습을 해야하나.. 오타가 많아서 큰일이다..

 

백준 1012번

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

1012번: 유기농 배추

 

이것 또한 라이님 블로그에 풀이가 있으니 참고참고🌽

 

// 1012번 유기농 배추
#define _CRT_SECURE_NO_WARNINGS
#include <cstdio>
#include <vector>
#include <algorithm>
using namespace std;

constexpr int MAX_N = 51;

class Graph {
public:
	int N, M;
	int arr[MAX_N][MAX_N] = { 0 };
	int dir_x[4] = { 0, 1, 0, -1 };
	int dir_y[4] = { 1, 0, -1, 0 };

	Graph() : N(0), M(0) {};
	Graph(int N, int M) : N(N), M(M) {}

	void addEdge(int x, int y) {
		arr[x][y] = 1;
	}
	int dfs_comp() {
		int comp = 0;
		for (int i = 0; i < M; i++) {
			for (int j = 0; j < N; j++) {
				if (arr[i][j]) {
					dfs(i, j);
					comp++;
				}
			}
		}
		return comp;
	}

private:
	void dfs(int x, int y) {
		arr[x][y] = 0;
		for (int i = 0; i < 4; i++) {
			if (isInside(x + dir_x[i], y + dir_y[i]) && arr[x + dir_x[i]][y + dir_y[i]]==1) {
				// ★dfs(x + dir_x[x], y + dir_y[y]),,, 
				arr[x + dir_x[i]][y + dir_y[i]] = 0;
				dfs(x + dir_x[i], y + dir_y[i]);
			}
		}

	}
	const bool isInside(const int x, const int y) {
		if (x < 0 || y < 0 || x >= M || y >= N) return false;
		return true;
	}
};
int main() {
	int T; scanf("%d", &T);
	vector<int> v;
	while (T--) {
		int M, N, K; scanf("%d %d %d", &N, &M, &K);
		Graph g(M, N);
		for (int i = 0; i < K; i++) {
			int x, y; scanf("%d %d", &x, &y);
			g.addEdge(x, y);
		}
		v.push_back(g.dfs_comp());
	}


	for (auto i : v) {
		printf("%d\n", i);
	}
	return 0;
}