[백준] 1012번 유기농 배추 (C++, BFS)

1인곳을 만나서 visit상태가 아니면 bfs를 돌린다. bfs돌리게 되는 횟수 = 지렁이 개수 

 

#define _CRT_SECURE_NO_DEPRECATE
#include <iostream>
#include <queue>
#include <tuple>
using namespace std;

#define MAX 51

int n,t,m,k;
int map[MAX][MAX];
bool vis[MAX][MAX];
int ypos[] = { 0,0,1,-1 };
int xpos[] = { 1,-1,0,0 };

int cnt = 0;

void bfs(int i,int j) {
	queue<pair<int, int>> q;
	q.push({ i,j });
	vis[i][j] = true;

	while (q.size() > 0) {
			int y, x;
			tie(y, x) = q.front();
			q.pop();

			for (int k = 0; k < 4; k++) {
				int yy = y + ypos[k];
				int xx = x + xpos[k];
				if (xx < 0 || yy < 0 || xx >= m || yy >= n)continue;
				if (map[yy][xx] == 0)continue;
				if (!vis[yy][xx]) {
					vis[yy][xx] = true;
					q.push({ yy,xx });
				}

			}

		}

}

int main(void) {

	ios::sync_with_stdio(false);
	cin.tie(NULL);

	cin >> t;
	for (int tc = 1; tc <= t; tc++) {
		int x, y;
		cnt = 0;
		for (int i = 0; i < n; i++) {
			memset(vis[i], false, sizeof vis[i]);
			memset(map[i], 0, sizeof map[i]);
		}

		cin >> m >> n >> k;
		
		for (int i = 0; i < k; i++) {
			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 && !vis[i][j]){
					cnt++;
					bfs(i, j);
				}
			}
		}
		

		cout <<cnt<<"\n";

	}


	return 0;
}