1. 개념

말 그대로 각각의 영역을 다른 색으로 Fill, 색칠한다고 보면 된다.
즉 다차원 배열의 어떤 칸과 연결된 영역을 찾는 알고리즘이다.

Flood Fill 개념 유튭

2. 풀이 방식

https://www.acmicpc.net/problem/2667
다음 문제를 통해 풀이 방식 차이에 대해 알아보자!

1) DFS

다음 코드 처럼 재귀적으로 DFS를 사용하여 해결할 수 있다.

//BFS
int dh[] = {-1, 1, 0, 0};
int dw[] = {0, 0, -1, 1};
void FloodFill(int h, int w){
    if (map[h][w]!='1')return;
    map[h][w] ='2';
    house++;
    for(int i = 0;i<4;i++){
        FloodFill(h+dh[i],w+dw[i]);
    }
}

int Solve(){
    int cnt = 0;
    for(int h=1;h<=N;h++){
        for(int j = 1;j<=N;j++){
             if(map[h][j]!='1')continue;
              house = 0;
              FloodFill(h,j);
              sol[cnt] = house;
              cnt++;
        }
    }
    return cnt;
}

2) BFS

좀더 구현이 복잡해서 보통 DFS를 사용해서 푼다.

int FloodFill(int h, int w){
	int cnt = 0;
    wp = rp = 0;
    push(h,w);
    cnt++;
    while(!empty()){
    	struct QUE cur = front(); pop();
        for(int i =0;i<4 ; i++){
        	int nh = cur.h + dh[i];
            int nw = cur.w + dw[i];
            if(map[nh][nw]!='1')continue;
            push(nh,nw);
            cnt++;
        }
    }
}
int SolveBFS(void){
	int cnt = 0;
    for(int h =1;h<=N;h++){
    	for(int w=1;w<=N;w++){
        	if(map[h][[w]!='1') continue;
            sol[cnt] = FloodFillBFS(h,w);
            cnt++;
        }
    }
    return cnt;
}

3. 문제 유형

모서리가 맞닿은 칸이 연결되어 있는 지에 따라서 4가지 방향 또는 8가지 방향이 있다.