[알고리즘][Recursion] Counting Cells in a Blob

1. Counting Cells in a Blob

• 이미지는 2개의 픽셀로 구성, 이미지 픽셀(image pixel) 또는 배경 픽셀(background pixcel)
• 서로 연결된 image pixcel들의 집합을 blob이라고 부름
• 상하좌우 및 대각 방향으로도 연결된 것으로 간주함

위 그림에서는 총 4개의 blob이 존재하고 각각의 크기는 5,5,13,1개입니다. 위 알고리즘의 문제는 입력으로 특정 좌표 (y,x)가 주어졌을 때 특정 좌표를 포함한 blob의 크기를 구하는 문제입니다. 예를 들어 (3,5)이 입력으로 주어졌을 때 blob의 크기는 13입니다.

 

입력

• N*N 크기의 2차원 그리드(grid)
• 하나의 좌표 (y,x)

출력

• 픽셀 (y,x)가 포함된 blob의 크기
• (y,x)가 어떤 blob에도 속하지 않는 경우에는 0 출력

 

2. 접근

• 현재 픽셀이 속한 blob의 크기를 카운트하려고 함
• 현재 픽셀이 image color가 아니라면 0을 반환
• 현재 픽셀이 image color인 경우
  • 현재 픽셀을 카운트(count=1)
  • 현재 픽셀이 중복 카운트 되는 것을 방지하기 위해 다른 색으로 칠함
  • 현재 픽셀에 이웃한 모든 픽셀(상하좌우, 대각방향)들에 대해서 그 픽셀이 속한 blob의 크기를 카운트하여 카운터에 더해준다.
  • 카운트를 반환

3. 수행과정

1. (y,x) = (3,5) 입력, count=0

(3,5) 픽셀이 포함된 blob의 크기를 계산하는 것이 목적

 

2. (3,5) 픽셀의 방문, count=1

(3,5) 픽셀을 방문하였으므로 중복 카운트를 방지하기 위해서 (3,5) 픽셀을 다른색으로 색칠합니다. 그리고 방문하였으므로 count를 1 증가시킵니다.

3. 인접한 픽셀 방문, 북쪽 방문

인접한 8개의 픽셀 각각에 대해서 순서대로 그 픽셀이 포함된 blob의 크기를 count합니다. 아래 그림에서 북쪽 픽셀이 포함된 blob의 크기는 0이다. 따라서 count 값은 변화없다.

4. 북동쪽 픽셀 방문

북동쪽 픽셀이 속한 blob을 count하고, count된 픽셀들을 색칠합니다.

3개의 픽셀이 blob에 속합니다. count를 3증가시켜줍니다.

5. 동쪽과 남동쪽 픽셀 방문

동쪽과 남동쪽 픽셀이 포함된 blob의 크기는 0이므로 count값의 변화는 없습니다.

6. 남쪽 픽셀 방문

남쪽 픽셀이 속한 blob의 크기는 9입니다. 카운트하고 색칠합니다.

7. 남서쪽, 서쪽, 북서 방향 픽셀 방문

픽셀이 속한 blob이 없거나 이미 방문한 픽셀이므로 카운트의 변화가 없습니다.

8. 결과

(3,5) 좌표를 포함한 blob의 크기는 13입니다.

 

4. 소스코드 구현

public class Blob {
	private static int N=8;
	private static int[][] image = {
			{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},
			
	};
	private static final int BACKGROUND_PIXCEL = 0; // 배경 픽셀
	private static final int IMAGE_PIXCEL = 1;	 	// 이미지 픽셀
	private static final int VISITED_PIXCEL = 2;	// 방문한 픽셀
	
	public static int countingCell(int y, int x)
	{
		if(y<0 || x<0 || y>=N || x>=N)
		{
			return 0;
		}
		else if(image[y][x]!=IMAGE_PIXCEL || image[y][x]==VISITED_PIXCEL)
		{
			return 0;
		}
		else 
		{
			image[y][x] = VISITED_PIXCEL;
			return 1 +
			countingCell(y-1, x) +
			countingCell(y-1, x+1) +
			countingCell(y, x+1) +
			countingCell(y+1, x+1) +
			countingCell(y+1, x) +
			countingCell(y+1, x-1) +
			countingCell(y, x-1) +
			countingCell(y-1, x-1);
			
		}
	}

	public static void main(String[] args) {
		System.out.println(countingCell(3,5));
	}
}

13

 

References

source code : https://github.com/yonghwankim-dev/inflearn_algorithm/tree/master/section02_Recursion_05
[인프런] 영리한 프로그래밍을 위한 알고리즘 강좌