[Algorithm] Recursion(재귀) : Counting cells in a blob

[Problem]

blob갯수 구하기. 아래 그림은 4개의 blob이 있다.

[Algorithm]

[Thinking]

recursion을 활용하여 선택된 셀 주위의 인접 image pixel을 확인해 카운트한다. 카운트 된 셀은 구분을 하기위해 빨간 셀로 표기한다.

[Result]

메인 함수의 코드이다.

int countCells(int (*grid)[8], int x,int y){  //grid함수 값 전달시 grid[][8]

if(x<0 || x>=8 || y<0 || y>=8)
return 0;
else if(grid[x][y]!=ImageC)
return 0;
else{
grid[x][y]=AlreadyC;
return 1 + countCells(grid,x-1,y+1) + countCells(grid,x,y+1)
                           + countCells(grid,x+1,y+1)+ countCells(grid,x-1,y)
                           + countCells(grid,x+1,y) + countCells(grid,x-1,y-1)
           + countCells(grid,x,y-1) + countCells(grid,x+1,y-1);
                                                                            //남서, 남, 남동
                                                                        //서, 동,
                                                                         //북서, 북, 북동
    }
}

x와 y에 0,0  즉 gird[0][0]의 blob의 크기를 구해보면 다음과 같다.



blob size는 5이고,
count된 blob은 2로 표기되어졋다.









다음은 전체 코드이다.

#include <stdio.h>

int BackgroundC = 0;  //흰 배경 셀
int ImageC = 1;       //파랑 배경 셀
int AlreadyC = 2;     //파랑 배경 셀에 한번 들른 경우 구별하기 위한 셀

int countCells(int (*grid)[8], int x,int y){  //grid함수 값 전달시 grid[][8]

if(x<0 || x>=8 || y<0 || y>=8) //1. 배열의 값을 넘어서는지 검사.
return 0;

else if(grid[x][y]!=ImageC)    //2. 셀이 빈 셀인지 검사.
return 0;

        else{
grid[x][y]=AlreadyC;    //3. 이미지셀일 경우 중복을 막기위해 체크하고
                                                   다시 재귀한다.
return 1 + countCells(grid,x-1,y+1) + countCells(grid,x,y+1)
                           + countCells(grid,x+1,y+1) + countCells(grid,x-1,y)
                           + countCells(grid,x+1,y) + countCells(grid,x-1,y-1)
   + countCells(grid,x,y-1) + countCells(grid,x+1,y-1);
                                                                            //남서, 남, 남동
                                            //서, 동,
                                                    //북서, 북, 북동
    }
}

int _tmain(int argc, _TCHAR* argv[])
{
int grid[8][8]={{1, 0, 0, 0, 0, 0, 0, 1},
   {0, 1, 1, 0, 0, 1, 0, 0},
   {1, 1, 0, 0, 1, 0, 1, 0},
             {0, 0, 0, 0, 0, 1, 0, 0},
   {0, 1, 0 ,1, 0, 1, 0, 0},
   {0, 1, 0 ,1, 0, 1, 0, 0},
   {1, 0, 0, 0, 1, 0, 0, 1},
   {0, 1, 1, 0, 0, 1, 1, 1}};

/*입력 받을 시
int s1,s2;
scanf("%d %d",&i,&j); //Grid의 열과 행을 입력받는다.
for(s1=0; s1<i; s1++){
for(s2=0; s2<j s2++){
scanf("%d",grid[s1][s2]);
}
}
*/

int i, j, result=0;   //행과열 반복문을 위한 변수i,j
       //blob size를 구하기위한 변수 result

for(i=0;i<8;i++){
for(j=0;j<8;j++){
result=countCells(grid,i,j);
if(result>0)
{
printf("%d\n",result);   //blob을 출력
}

}
}

for(i=0;i<8;i++){           //전체배열을 출력
for(j=0;j<8;j++){
printf("%d ",grid[i][j]);
}
printf("\n");
}
return 0;
}


결과창