[백준] 1012. 유기농 배추

1012. 유기농 배추

간단한 dfs, bfs 문제이다.
DFS 깊이 우선 탐색 방식으로 문제를 풀었다.

이중배열인 map과 check를 선언한다.
map은 배추의 위치를, check는 확인을 하면 true, 하지 않으면 false.

1. 이중 for문으로 map을 돌면서 배추가 있고, check가 false이면 dfs를 돈다.
   • check를 true로 바꾸고, 동서남북을 확인해서 dfs를 반복한다.

#include <iostream>
using namespace std;
int dirX[4] = { 1,-1,0,0 };
int dirY[4] = { 0,0,1,-1 };
int map[51][51];
int t, m, n, k, cnt = 0;
bool check[51][51];
void clear_map() {
	for (int i = 0; i < 51; i++)
		for (int j = 0; j < 51; j++) {
			map[i][j] = 0;
			check[i][j] = false;
		}
}

bool in_map(int y, int x) {
	if (y >= 0 && y < n && x >= 0 && x < m)
		return true;
	return false;
}

void dfs(int y, int x) {
	check[y][x] = true;
	for (int i = 0; i < 4; i++) {
		int movex = x + dirX[i], movey = y + dirY[i];
		if (map[movey][movex] == 1 && !check[movey][movex] && in_map(movey, movex)) {
			dfs(movey, movex);
		}
	}
}

int main() {
	cin >> t;
	while (t) {
		t--;
		cin >> m >> n >> k;
		for (int i = 0; i < k; i++) {
			int x, y;
			cin >> x >> y;
			map[y][x] = 1;
		}

		for (int i = 0; i < n; i++) {
			for (int j = 0; j < m; j++) {
				if (map[i][j] == 1 && !check[i][j]) {
					dfs(i, j);
					cnt++;
				}
			}
		}
		cout << cnt << endl;
		clear_map();
		cnt = 0;
	}
}