Counting cells in a Blob_v1 c++

nhn pre-test1 모의 테스트 예시 보다가 예전에 학교 다닐 때 공부했던 걸 급하게 다시 정리한다!

Recursion 을 공부할 때 주로 다뤘던 내용인데,
크기가 8 x 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},

이 주어졌다고 하자.

여기서 인접한 1들을 한 Blob 으로 묶고 Blob의 갯수와 각 Blob안에 cell의 갯수를 카운트 하는 문제다.

그림을 보면 총 4개의 Blob이 있고 각 Blob에는 5, 1, 13, 5 개의 cell이 있다.

먼저 현재 픽셀이 속한 Blob의 크기를 카운트 하려면
1. x,y=!1이면 return 0 (색칠된 칸이 아니면 return 0)
2. x,y=1 이면 현재 픽셀을 카운트
2-1. 현재 픽셀이 중복 카운트 되는 것을 막기 위해 표시 (already counted)
2-2. 현재 픽셀에 이웃한 모든 픽셀들에 대해 그 픽셀이 속한 blob의 크기를 카운트하여 카운터에 더해줌.

1. x,y 좌표를 선택하고 해당 Blob에 몇 개의 Cell이 있는지 구하는 코드

#include<stdio.h>

const 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},
};

const int BACKGROUND_COLOUR = 0;
const int IMANGE_COLOUR = 1;
const int ALREADY_COUNTED = 2;

int countCells(int x, int y) {
	if (x < 0 || y<0 || x >= N || y>N)
		return 0;

	else if (grid[x][y] != IMANGE_COLOUR)
		return 0;

	else {
		grid[x][y] = ALREADY_COUNTED;

		return 1 + countCells(x, y - 1) + countCells(x + 1, y - 1) + countCells(x + 1, y)
			+ countCells(x + 1, y + 1) + countCells(x, y + 1) + countCells(x - 1, y + 1)
			+ countCells(x - 1, y) + countCells(x - 1, y - 1);
	}
}

int main() {
	int x, y;

	printf("insert the x,y point : ");
	scanf_s("%d %d", &x, &y);
	printf("It has %d bolocks in this Blob. \n", countCells(x, y));

	return 0;
}

2. 총 몇 개의 Blob이 있으며 각 Blob에 몇 개의 Cell이 있는지 구하는 코드

#include<iostream>
#include<vector>

using namespace std;

const int N = 8;
vector<int> list(N);
int nList = 0;

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},
};

const int BACKGROUND_COLOUR = 0;
const int	 IMANGE_COLOUR = 1;
const int ALREADY_COUNTED = 2;

int countCells(int x, int y) {
	if (x < 0 || y<0 || x >= N || y>=N)
		return 0;

	else if (grid[x][y] != IMANGE_COLOUR)
		return 0;

	else {
		grid[x][y] = ALREADY_COUNTED;

		return 1 + countCells(x, y - 1) + countCells(x + 1, y - 1) + countCells(x + 1, y)
			+ countCells(x + 1, y + 1) + countCells(x, y + 1) + countCells(x - 1, y + 1)
			+ countCells(x - 1, y) + countCells(x - 1, y - 1);
	}
}

void solution() {
	for (int i = 0; i < N; i++) {
		for (int j = 0; j < N; j++) {
			if (grid[i][j] == IMANGE_COLOUR) {
				list[nList++]=countCells(i, j);
			}
		}
	}

	cout << nList << endl;
	for (int i = 0; i < nList; i++) 
		cout << list[i] << " ";

}

int main() {

	solution();

	return 0;
}