Recursion의 응용 : Counting Cells in a Bob

- 입력으로 하나의 Binary 이미지를 받는다.

- 각 픽셀은 background pixel 이거나 혹은 image pixel

- 서로 연결된 image pixel들의 집합을 blob이라고 부름

- 상하좌우 및 대각방향으로도 연결된 것으로 간주

 

https://www.youtube.com/watch?v=HHJFlVT1tBw&list=PL52K_8WQO5oUuH06MLOrah4h05TZ4n38l&index=5

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

 

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

 

---

 

Recursive Thinking

 

현재 픽셀이 이 속한 blob의 크기를 카운트 하려면

    현재 픽셀이 image color가 아니라면

        0을반환

    현재 픽셀이 image color 라면

        먼저 현재 픽셀을 카운트한다.

        현재 픽셀이 중복 체크되는 것을 방지하기 위해 다른 색으로 칠한다.

        현재 픽셀에 이웃한 모든 픽셀들에 대해서 

            그 픽셀이 속한 blob의 크기를 카운트하여 카운터에 더해준다.

        카운터를 반환한다.

 

	private static void dfs(int x,int y) {
		
		if(x < 0 || x >= n || y < 0 || y >= n) {
			return;
		}
		
		visited[x][y] = true;
		count++;
		
		for(int i=0; i<8; i++) {
			int nx = x+dx[i];
			int ny = y+dy[i];
			
			if(nx < 0 || nx >= n || ny < 0 || ny >= n)
				continue;
			if(arr[nx][ny]==1&&!visited[nx][ny]) {
				dfs(nx,ny);
			}
		}
	}

직접 짜본 코드이다. 강의 보다 더 보기쉽게 구현하였다.