[recursion 응용] Counting Cells in a Blob

 

Blob에 대한 이해를 해보자.

- 각 픽셀은 background pixel이거나, image pixel이다.

- 서로 연결된 image pixel을 blob이라 한다.

(이때 상하좌우, 대각방향으로 연결된 것을 모두 셈한다.)

회색으로 묶은 것이 blob

 

 

만들 함수의 입,출력을 정하자.

- 입력: N*N 크기의 2차원 그리드와 하나의 좌표 (x,y)

- 출력: 픽셀 (x,y)가 포함된 blob의 크기.

(이때, (x,y)가 어떤 blob에도 포함되지 않는 경우는 0을 반환한다.)

 

 

recursion thinking 하면서 코드 대략 정하기

현재 픽셀이 이 속한 blob의 크기를 카운트하려면
	현재 픽셀이 image colour이 아니라면
    	0을 반환한다
    현재 픽셀이 image colour라면
    	먼저 현재 픽셀을 카운트한다 (count=1).
        현재 픽셀이 중복 카운트되는 것을 방지하기 위해 다른 색으로 칠한다.
        현재 픽셀에 이웃한 모든 픽셀들에 대해서
        	그 픽셀이 속한 blob의 크기를 카운트하여 카운터에 더해준다.
        카운터를 반환한다.

Algorithm for countCells(x, y)
if the pixel(x, y) is outside the grid
	the result is 0;
else if pixel(x, y) is not an image pixel or already counted
	the result is 0;
else {
	set the colour of the pixel(x, y) to a red colour;
	the result is 1 plus the number of cells in each piece of
		the blob that includes a nearest neighbor;

---

 

픽셀이 계산되는 방식

 

---

완성된 코드

#include <iostream>
using namespace std;
int BACKGROUND_COLOUR = 0;
int IMAGE_COLOUR = 1;
int ALREADY_COUNTED = 2;

int countCells(int x, int y) {
	int N;
	int grid[10][10];
	if (x <= 0 || x >= N || y < 0 || y >= N)
		return 0;
	else if (grid[x][y] != IMAGE_COLOUR)
		return 0;
	else {
		grid[x][y] = ALREADY_COUNTED;
		return 1 + countCells(x - 1, y + 1) + countCells(x, y + 1)
			+ countCells(x + 1, y + 1) + countCells(x - 1, y)
			+ countCells(x + 1, y) + countCells(x - 1, y - 1)
			+ countCells(x, y - 1) + countCells(x + 1, y - 1);
	}
}

---

알고리즘을 이해는 하겠는데, 추가적인 코딩 실력이 부족해 main함수까지 완성을 못하겠다.

이거슨 c++의 class랑 c언어의 구조체를 헷갈려하는 내 죄야.,,

중간에 참고하려고 작년에 c++공부한 걸 봤다가 깜짝 놀랐다. 다 까먹었기 때문.

얼른 c랑 c++복습할 겸 업로드를 해야겠다.