[C++] BOJ-1012

 

문제풀이

---

배추를 찾은 후 BFS로 탐색

서로 떨어져 있는 배추를 찾을때마다 count 해주는 방식으로 문제 해결

 

 

 

#include <iostream>
#include <queue>

using namespace std;

int map[51][51];

int dx[4] = {0,0,-1,1}; // 상하좌우 
int dy[4] = {1,-1,0,0};
queue< pair<int, int> > q;
int T,N,M,K;
int X,Y;

int bfs(){
	int cnt = 0;
	
	for(int i = 0; i<N; i++){
		for(int j = 0; j<M; j++){
			
			if(map[i][j] == 1){
				map[i][j] == 0;
//				cout << i << j << endl;
				q.push(make_pair(i,j));
				while(!q.empty()){
					
					int x = q.front().first;
					int y = q.front().second;
					q.pop();
					
					for(int k = 0; k<4; k++){
						int rx = x + dx[k];
						int ry = y + dy[k];
						if(rx>=0 && ry >= 0 && rx < N && ry < M){
							if(map[rx][ry] == 1){
								map[rx][ry] = 0;
								q.push(make_pair(rx,ry));
							}
						}
					}
				}
				cnt++;
			}
		}
	}
	return cnt;
}

int main() {
	cin >> T;
	for(int Test_case = 0; Test_case<T; Test_case++){
		cin >> M >> N >> K;
		for(int i = 0; i<K; i++){
			cin >> X >> Y;
			map[Y][X] = 1;
		}
		cout << bfs() << "\n";
		
		for(int i = 0; i<N; i++){
			for(int j = 0; j<M; j++){
				map[i][j] = 0;
			}
		}
	}
	
}