알고리즘22 :: 플러드 필&BOJ_2677_단지번호붙이기

어떤 위치와 연결된 모든 위치를 찾는 알고리즘이다. 

BOJ :: 2667 단지 번호 붙이기 문제가 대표적이다.

연결요소 를 고려해보면 된다. 

단지의 개수와 크기를 구하면 된다. 

이차원 배열 상에서 상, 하, 좌, 우 를 고려한 배열이기 때문에 추가적인 자료구조가 필요하지 않다.

BOJ_2677_단지번호붙이기가 대표적인 예이다.

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57

#include <cstdio> #include <algorithm> #include <queue> using namespace std; int a[30][30]; int group[30][30]; int dx[] = {0,0,1,-1}; int dy[] = {1,-1,0,0}; int n; int ans[25*25]; void bfs(int x, int y, int cnt) {     queue<pair<int,int>> q;     q.push(make_pair(x,y));     group[x][y] = cnt;     while (!q.empty()) {         x = q.front().first;         y = q.front().second;         q.pop();         for (int k=0; k<4; k++) {             int nx = x+dx[k];             int ny = y+dy[k];             if (0 <= nx && nx < n && 0 <= ny && ny < n) {                 if (a[nx][ny] == 1 && group[nx][ny] == 0) {                     q.push(make_pair(nx,ny));                     group[nx][ny] = cnt;                 }             }         }     } } int main() {     scanf("%d",&n);     for (int i=0; i<n; i++) {         for (int j=0; j<n; j++) {             scanf("%1d",&a[i][j]);         }     }     int cnt = 0;     for (int i=0; i<n; i++) {         for (int j=0; j<n; j++) {             if (a[i][j] == 1 && group[i][j] == 0) {                 bfs(i, j, ++cnt);             }         }     }     printf("%d\n",cnt);     for (int i=0; i<n; i++) {         for (int j=0; j<n; j++) {             ans[group[i][j]]+=1;         }     }     sort(ans+1, ans+cnt+1);     for (int i=1; i<=cnt; i++) {         printf("%d\n",ans[i]);     }     return 0; }