[Recursion] Counting Cells in a Blob

 

이 문제는 위 표에서 보이는 0과 1로 구분된 이미지인 binary image를 가진다. 파란색은 image pixel(1), 흰 색은 background pixel(0)이라고 할 때, 상하좌우 및 대각선방향으로 서로 연결된 image pixel들의 집합을 blob라고 한다.

이 문제는 특정 위치 (x, y)에서 blob이 존재하면 그 blob의 셀 개수를 계산하는 문제다.

Solving problem

1. 주어진 위치가 존재하는지 여부 판별
   - x 혹은 y의 값이 범위를 넘어갈 경우 0을 반환
2. 주어진 위치가 image pixel 아닌 판별
   - image pixel이 아닌 경우 0을 반환
   - blob를 구해야하기 때문에 image pixel이 아닌 경우 필요 없음.
3. 위 조건들이 모두 일치하지 않을 경우, 주어진 위치는 image pixel이므로 이 픽셀을 포함하고, 상하좌우 및 대각선방향의 pixel들을 확인한다.
   - 지났던 image pixel은 구분하기 위해 checked 값을 넣어 분류해준다.

---

#include <iostream>

using namespace std;

int n = 8;

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 bg = 0;
int image = 1;
int checked = 2;

int count_cells(int x, int y){

	if(x<0 || y<0 || x>=n || y>=n)
		return 0;
	else if(grid[x][y] != image)
		return 0;
	else{
		grid[x][y] = checked;
		return 1 + count_cells(x-1, y+1) + count_cells(x, y+1) 
        		+ count_cells(x+1, y+1) + count_cells(x-1, y) + count_cells(x+1, y) 
        		+ count_cells(x-1, y-1) + count_cells(x, y-1) + count_cells(x+1, y-1);	
	}
}

int main(){

	cout << count_cells(0, 0);

	return 0;
}

2015 봄학기 알고리즘 강의노트