음료수 얼려 먹기 - 이코테 DFS/BFS 문제

https://www.youtube.com/watch?v=7C9RgOcvkvo

이 문제는 dfs/bfs로 풀리는 문제이다.

우선 0이 있는 부분을 한 뭉탱이로 탐색해야 한다.

뭉탱이로 만들기 위해 그래프에 있는 0에 대해 dfs를 재귀적으로 수행한다.

그러면 0들이 상하좌우로 모여있는 뭉탱이들이 방문 처리가 되어
뭉탱이의 개수를 셀 수 있다.

코드는 다음과 같다.

#include <bits/stdc++.h>
#define MAX 1000+1
using namespace std;

int N;
int M;
int ans=0;

bool graph[MAX][MAX];

bool dfs(int x, int y){
	if(N<=x || x<=-1 || M<=y || y<=-1){
		return false;
	}
	
	if(not graph[x][y]){
		graph[x][y]=true;
		
		dfs(x-1,y);
		dfs(x+1,y);
		dfs(x,y-1);
		dfs(x,y+1);
		return true;
	}
	return false;
}

int main(){
	ios_base :: sync_with_stdio(false); cin.tie(NULL);
	
	cin >> N >> M;
	for(int i=0;i<N;i++){
		for(int j=0;j<M;j++){
			scanf("%1d",&graph[i][j]);
		}
	}
	for(int i=0;i<N;i++){
		for(int j=0;j<M;j++){
			if(dfs(i,j)){
				ans++;
			}
		}
	}
	cout << ans;
}