[ C++ ] #1012 유기농 배추

이번에는 몇모둠이 있나?에 대한 문제이다.

1을 찾아서 BFS를 진행하고 또 1을 찾아서 BFS를 하고

이런식으로 반복하면 금방 개수를 알 수 있지 않을까? 하는 생각이 들었다.

 

코딩해보자~!

 

우왕!! 한번에 맞았다.

디테일이 부족해서 계속 while문을 돌아 여러번에 디버깅이 필요햇지만

그래도 크게 어려움을 겪지 않고 성공했다!

 

#include<iostream>
#include<queue>
#include<vector>

using namespace std;

int farm[50][50];
int dx[4] = { 1,0,-1,0 };
int dy[4] = { 0,1,0,-1 };

int main() {

	int a, num = 0,N, M ,K, x, y, flag = 0,sx,sy;
	cin >> a;

	for (int i = 0; i < a; i++) {  //테스트케이스만큼
		num = 0;
		queue<pair<int, int>> Q;
		flag = 0;

		cin >> M >> N >> K;

		for (int j = 0; j < K; j++) {  //입력받기
			cin >> y >> x;
			farm[x][y] = 1;
		}

		while (flag == 0) {  //개수세기

			for (int a = 0; a < N; a++) {  //1찾기
				for (int b = 0; b < M; b++) {
					if (farm[a][b] == 1) { Q.push({ a,b }); farm[a][b] = 0; goto start; }
				}
			} flag = 1; continue;  //한번의 테스트케이스 종료

		start:  //BFS진행

			while (!Q.empty()) {
				pair<int, int > C = Q.front();
				Q.pop();

				for (int j = 0; j < 4; j++) {
					int nx = C.first + dx[j];
					int ny = C.second + dy[j];

					if (nx < 0 || nx >= N || ny < 0 || ny >= M) continue;
					if (farm[nx][ny] == 0) continue;

					Q.push({ nx,ny });
					farm[nx][ny] = 0;
				}
			} num++;
		}
		cout << num << "\n";
	}

}