유기농 배추 C++ - 백준 1012

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

이 문제는 전에 다뤘던 이코테의 음료수 얼려먹기와 유사하다.

코드는 다음과 같다.

#include <bits/stdc++.h>
using namespace std;

int T;
int N;
int M;
int K;
int pos[2];
int ans;
int dx[4]={1,-1,0,0};
int dy[4]={0,0,1,-1};

bool graph[51][51];

bool dfs(int x, int y){
	if(N<=x || x<0 || M<=y || y<0){
		return false;
	}
	
	if(!graph[x][y]){
		return false;
	}
	
	graph[x][y]=false;
	for(int i=0;i<4;i++){
		dfs(x+dx[i],y+dy[i]);
	}
	return true;
}

int main(){
	ios_base :: sync_with_stdio(false); cin.tie(NULL);
	
	cin >> T;
	for(int i=0;i<T;i++){
		cin >> N >> M >> K;
		ans=0;
		for(int j=0;j<K;j++){
			cin >> pos[0] >> pos[1];
			graph[pos[0]][pos[1]]=true;
		}
		for(int j=0;j<N;j++){
			for(int k=0;k<M;k++){
				if(dfs(j,k)){
					ans++;
				}
			}
		}
		cout << ans << '\n';
	}
}

음료수 얼려먹기와 같이 graph에 있는 모든 원소를 탐색하며 dfs를 돌리고, 만약 dfs값이 true면 배추흰지렁이의 개수를 증가시켰다.