Blob 셀 개수 세기 알고리즘 (재귀함수 응용)

티스토리 뷰

컴퓨터 공부방/알고리즘

Blob 셀 개수 세기 알고리즘 (재귀함수 응용) - JAVA

Digest 2019. 9. 11. 00:27

개인적으로 미로 알고리즘 다음으로 재귀적인 사고방식을 갖게 해 준 알고리즘인 것 같다. 재귀적인 함수 사고를 갖기란 정말 쉽지가 않은 것 같다. 훈련을 여러 번 거듭하면서 비로소 재귀적인 사고가 가능해질 것 같다는 생각이 든다. 이번에는 좀 생소한 Blob이라는 개념을 가지고 알고리즘을 코딩해보도록 하겠다.

미로찾기 알고리즘 (재귀함수 응용문제) JAVA

개인적으로 재귀함수적인 사고를 할 수 있도록 도와 준 정말 고마운 알고리즘이라고 생각한다. 아무래도 재귀함수적인 사고에 익숙하지 않기 때문에 이런 훈련이 필요하다고 생각은 했다. 재귀함수는 팩토리얼과..

digest1.tistory.com

Rules of Counting cells in a Blob

잠깐!! 여기서 Blob이란?

Binary large object, BLOB은 데이터베이스에서 하나의 엔티티로서 저장되는 이진데이터의 모음이라고 위키백과에서는 설명하고 있다. 보통 사진과 같은 그림파일이나 사운드 파일, 그리고 멀티미디어 개체 파일을 저장할 수 있고 바이너리 실행 코드 또한 이 파일 형식으로 저장이 된다고 설명한다. 설명은 이정도에서 간추리도록 하고, 이제 Blob이라는 개념으로 어떤 알고리즘을 짤 것인지에 관해 살펴보도록 하자.

바이너리 라지 오브젝트 - 위키백과, 우리 모두의 백과사전

위키백과, 우리 모두의 백과사전. 바이너리 라지 오브젝트(Binary large object, BLOB)는 데이터베이스 관리 시스템의 하나의 엔티티로서 저장되는 이진 데이터의 모임이다. BLOB은 일반적으로 그림, 오디오, 또는 기타 멀티미디어 오브젝트인 것이 보통이지만, 바이너리 실행 코드가 BLOB으로 저장되기도 한다. BLOB에 대한 데이터베이스 지원은 보편적인 것은 아니다. 자료형과 정의는 전통적인 컴퓨터 데이터베이스 시스템에 본래 정의되지 않은

ko.wikipedia.org

문제 확인

다음 중 음영이 있는 칸은 Blob 데이터가 있는 구간이다. Blob 데이터의 개수와 크기를 구하시오.

특정 데이터를 기준으로 대각선이나 상하좌우에 있는 데이터는 이어진 것으로 본다.
특정 데이터가 이어진 개수만큼을 크기라고 한다.

import java.util.ArrayList;

public class Blob {
	private static int N=8;
	private final static int BACKGROUND_COLOR = 0;
	private final static int IMAGE_COLOR = 1;
	private final static int ALREADY_COUNTED = 2;
	private static int[][] blob= {
		{1,1,0,0,0,0,0,1},
		{0,1,1,0,0,0,0,0},
		{0,0,1,1,0,0,1,0},
		{0,0,0,1,0,1,0,1},
		{0,0,1,0,0,0,1,0},
		{0,0,0,0,0,0,1,0},
		{0,0,1,0,0,0,0,1},
		{1,1,0,0,0,0,1,0},
	};
	
	public static int countCells(int x, int y) {
		System.out.format("(%d, %d) 좌표 스캔 중\n",x,y);

		if(x<0 || y<0 || x>=N || y>=N) {
			//X나 Y의 범위가 밖으로 넘어가 버리면?
			return 0;
		}else if(blob[x][y]!=IMAGE_COLOR || blob[x][y]==ALREADY_COUNTED) {
			return 0;
		}else {
			printBlob();
			blob[x][y]=ALREADY_COUNTED;
			printBlob();
			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);
		}
	}
	
	public static ArrayList<Integer> explore() {
		ArrayList<Integer> blobSize=new ArrayList<Integer>();
		for(int x=0;x<N;x++) {
			for(int y=0;y<N;y++) {
				if(blob[x][y]==IMAGE_COLOR) {
					blobSize.add(countCells(x,y));
					System.out.format("(%d,%d)로 시작하는 blob의 크기는 %d\n", x,y,blobSize.get(blobSize.size()-1));
				}
			}
		}
		return blobSize;
	}
	
	public static void printBlob() {
		for(int i=0;i<blob.length;i++) {
			for(int j=0;j<blob[i].length;j++) {
				System.out.print(blob[i][j]+ " ");
			}
			System.out.println("");
		}
		System.out.println("");
	}
	
	public static void main(String[] args) {
		ArrayList<Integer> blobSize=new ArrayList<Integer>();
		printBlob();
		Blob b = new Blob();
		blobSize = b.explore();
		printBlob();
		System.out.format("최종 blob의 개수는 %d\n", blobSize.size());
		for(int i:blobSize) {
			System.out.println("크기가 " + i);
		}
	}
}

접근 방법

이것도 마찬가지로 미로 때와 비슷한 발상으로 진행하지만 이건 조금 방식이 다르다. 대각선으로도 인접한 부분을 포함시켜서 탐색을 해야 한다는 점이 다르다. 그렇다면 수기로 한 번 풀어보자! 다만, 수기로 직접 푼 결과화면을 직접 스캔해서 올리는 것이니, 순서는 아래의 풀이를 참조하시기 바란다.

사람이 푸는 방식

이미지 데이터는 1이고, 그 밖의 값은 0이다. (0은 위에서 생략하였음.)
탐색은 (x=0,y=0) 좌표부터 할 것이고, 재귀호출을 통해 이어진 데이터가 있는지 확인할 것이다.
이어진 데이터는 상하좌우 대각선이며, 이어진 데이터가 있으면 또 이어진 데이터가 있는지 재귀적으로 호출한다.

기계가 푸는 방식

정답인 코드에 보면 다음과 같은 순서로 인접한 셀을 검사하기로 하였다.

검사지점을 기준으로 인접한 셀을 다음과 같은 순서로 검사할 경우 스택에는 아래의 우측과 같은 방식으로 값이 쌓이게 된다고 볼 수 있다.

프로그램 코드에 따라 어떻게 움직이는지를 그림을 통해 디버깅 모습을 확인해 보았다. 재귀호출이 확실히 헷갈렸는데, 이를 헷갈리지 않도록 바로잡는 방법을 연구했더니 그것은 바로 스택을 떠올리는 것이다. 재귀호출=스택!!!!! 재귀호출은 스택에 차곡차곡 호출할 메서드를 쌓아가는 방식이다. 그리고 위에서부터 하나씩 차근차근 풀어간다는 것을 떠올리면 이내 정리가 될 것이다.

1 1 0 0 0 0 0 1 
0 1 1 0 0 0 0 0 
0 0 1 1 0 0 1 0 
0 0 0 1 0 1 0 1 
0 0 1 0 0 0 1 0 
0 0 0 0 0 0 1 0 
0 0 1 0 0 0 0 1 
1 1 0 0 0 0 1 0 

(0, 0) 좌표 스캔 중
1 1 0 0 0 0 0 1 
0 1 1 0 0 0 0 0 
0 0 1 1 0 0 1 0 
0 0 0 1 0 1 0 1 
0 0 1 0 0 0 1 0 
0 0 0 0 0 0 1 0 
0 0 1 0 0 0 0 1 
1 1 0 0 0 0 1 0 

2 1 0 0 0 0 0 1 
0 1 1 0 0 0 0 0 
0 0 1 1 0 0 1 0 
0 0 0 1 0 1 0 1 
0 0 1 0 0 0 1 0 
0 0 0 0 0 0 1 0 
0 0 1 0 0 0 0 1 
1 1 0 0 0 0 1 0 

(0, -1) 좌표 스캔 중
(1, -1) 좌표 스캔 중
(1, 0) 좌표 스캔 중
(1, 1) 좌표 스캔 중
2 1 0 0 0 0 0 1 
0 1 1 0 0 0 0 0 
0 0 1 1 0 0 1 0 
0 0 0 1 0 1 0 1 
0 0 1 0 0 0 1 0 
0 0 0 0 0 0 1 0 
0 0 1 0 0 0 0 1 
1 1 0 0 0 0 1 0 

2 1 0 0 0 0 0 1 
0 2 1 0 0 0 0 0 
0 0 1 1 0 0 1 0 
0 0 0 1 0 1 0 1 
0 0 1 0 0 0 1 0 
0 0 0 0 0 0 1 0 
0 0 1 0 0 0 0 1 
1 1 0 0 0 0 1 0 

(1, 0) 좌표 스캔 중
(2, 0) 좌표 스캔 중
(2, 1) 좌표 스캔 중
(2, 2) 좌표 스캔 중
2 1 0 0 0 0 0 1 
0 2 1 0 0 0 0 0 
0 0 1 1 0 0 1 0 
0 0 0 1 0 1 0 1 
0 0 1 0 0 0 1 0 
0 0 0 0 0 0 1 0 
0 0 1 0 0 0 0 1 
1 1 0 0 0 0 1 0 

2 1 0 0 0 0 0 1 
0 2 1 0 0 0 0 0 
0 0 2 1 0 0 1 0 
0 0 0 1 0 1 0 1 
0 0 1 0 0 0 1 0 
0 0 0 0 0 0 1 0 
0 0 1 0 0 0 0 1 
1 1 0 0 0 0 1 0 

(2, 1) 좌표 스캔 중
(3, 1) 좌표 스캔 중
(3, 2) 좌표 스캔 중
(3, 3) 좌표 스캔 중
2 1 0 0 0 0 0 1 
0 2 1 0 0 0 0 0 
0 0 2 1 0 0 1 0 
0 0 0 1 0 1 0 1 
0 0 1 0 0 0 1 0 
0 0 0 0 0 0 1 0 
0 0 1 0 0 0 0 1 
1 1 0 0 0 0 1 0 

2 1 0 0 0 0 0 1 
0 2 1 0 0 0 0 0 
0 0 2 1 0 0 1 0 
0 0 0 2 0 1 0 1 
0 0 1 0 0 0 1 0 
0 0 0 0 0 0 1 0 
0 0 1 0 0 0 0 1 
1 1 0 0 0 0 1 0 

(3, 2) 좌표 스캔 중
(4, 2) 좌표 스캔 중
2 1 0 0 0 0 0 1 
0 2 1 0 0 0 0 0 
0 0 2 1 0 0 1 0 
0 0 0 2 0 1 0 1 
0 0 1 0 0 0 1 0 
0 0 0 0 0 0 1 0 
0 0 1 0 0 0 0 1 
1 1 0 0 0 0 1 0 

2 1 0 0 0 0 0 1 
0 2 1 0 0 0 0 0 
0 0 2 1 0 0 1 0 
0 0 0 2 0 1 0 1 
0 0 2 0 0 0 1 0 
0 0 0 0 0 0 1 0 
0 0 1 0 0 0 0 1 
1 1 0 0 0 0 1 0 

(4, 1) 좌표 스캔 중
(5, 1) 좌표 스캔 중
(5, 2) 좌표 스캔 중
(5, 3) 좌표 스캔 중
(4, 3) 좌표 스캔 중
(3, 3) 좌표 스캔 중
(3, 2) 좌표 스캔 중
(3, 1) 좌표 스캔 중
(4, 3) 좌표 스캔 중
(4, 4) 좌표 스캔 중
(3, 4) 좌표 스캔 중
(2, 4) 좌표 스캔 중
(2, 3) 좌표 스캔 중
2 1 0 0 0 0 0 1 
0 2 1 0 0 0 0 0 
0 0 2 1 0 0 1 0 
0 0 0 2 0 1 0 1 
0 0 2 0 0 0 1 0 
0 0 0 0 0 0 1 0 
0 0 1 0 0 0 0 1 
1 1 0 0 0 0 1 0 

2 1 0 0 0 0 0 1 
0 2 1 0 0 0 0 0 
0 0 2 2 0 0 1 0 
0 0 0 2 0 1 0 1 
0 0 2 0 0 0 1 0 
0 0 0 0 0 0 1 0 
0 0 1 0 0 0 0 1 
1 1 0 0 0 0 1 0 

(2, 2) 좌표 스캔 중
(3, 2) 좌표 스캔 중
(3, 3) 좌표 스캔 중
(3, 4) 좌표 스캔 중
(2, 4) 좌표 스캔 중
(1, 4) 좌표 스캔 중
(1, 3) 좌표 스캔 중
(1, 2) 좌표 스캔 중
2 1 0 0 0 0 0 1 
0 2 1 0 0 0 0 0 
0 0 2 2 0 0 1 0 
0 0 0 2 0 1 0 1 
0 0 2 0 0 0 1 0 
0 0 0 0 0 0 1 0 
0 0 1 0 0 0 0 1 
1 1 0 0 0 0 1 0 

2 1 0 0 0 0 0 1 
0 2 2 0 0 0 0 0 
0 0 2 2 0 0 1 0 
0 0 0 2 0 1 0 1 
0 0 2 0 0 0 1 0 
0 0 0 0 0 0 1 0 
0 0 1 0 0 0 0 1 
1 1 0 0 0 0 1 0 

(1, 1) 좌표 스캔 중
(2, 1) 좌표 스캔 중
(2, 2) 좌표 스캔 중
(2, 3) 좌표 스캔 중
(1, 3) 좌표 스캔 중
(0, 3) 좌표 스캔 중
(0, 2) 좌표 스캔 중
(0, 1) 좌표 스캔 중
2 1 0 0 0 0 0 1 
0 2 2 0 0 0 0 0 
0 0 2 2 0 0 1 0 
0 0 0 2 0 1 0 1 
0 0 2 0 0 0 1 0 
0 0 0 0 0 0 1 0 
0 0 1 0 0 0 0 1 
1 1 0 0 0 0 1 0 

2 2 0 0 0 0 0 1 
0 2 2 0 0 0 0 0 
0 0 2 2 0 0 1 0 
0 0 0 2 0 1 0 1 
0 0 2 0 0 0 1 0 
0 0 0 0 0 0 1 0 
0 0 1 0 0 0 0 1 
1 1 0 0 0 0 1 0 

(0, 0) 좌표 스캔 중
(1, 0) 좌표 스캔 중
(1, 1) 좌표 스캔 중
(1, 2) 좌표 스캔 중
(0, 2) 좌표 스캔 중
(-1, 2) 좌표 스캔 중
(-1, 1) 좌표 스캔 중
(-1, 0) 좌표 스캔 중
(2, 2) 좌표 스캔 중
(2, 3) 좌표 스캔 중
(1, 3) 좌표 스캔 중
(1, 2) 좌표 스캔 중
(1, 1) 좌표 스캔 중
(1, 2) 좌표 스캔 중
(0, 2) 좌표 스캔 중
(0, 1) 좌표 스캔 중
(0, 0) 좌표 스캔 중
(0, 1) 좌표 스캔 중
(-1, 1) 좌표 스캔 중
(-1, 0) 좌표 스캔 중
(-1, -1) 좌표 스캔 중
(0,0)로 시작하는 blob의 크기는 8
(0, 7) 좌표 스캔 중
2 2 0 0 0 0 0 1 
0 2 2 0 0 0 0 0 
0 0 2 2 0 0 1 0 
0 0 0 2 0 1 0 1 
0 0 2 0 0 0 1 0 
0 0 0 0 0 0 1 0 
0 0 1 0 0 0 0 1 
1 1 0 0 0 0 1 0 

2 2 0 0 0 0 0 2 
0 2 2 0 0 0 0 0 
0 0 2 2 0 0 1 0 
0 0 0 2 0 1 0 1 
0 0 2 0 0 0 1 0 
0 0 0 0 0 0 1 0 
0 0 1 0 0 0 0 1 
1 1 0 0 0 0 1 0 

(0, 6) 좌표 스캔 중
(1, 6) 좌표 스캔 중
(1, 7) 좌표 스캔 중
(1, 8) 좌표 스캔 중
(0, 8) 좌표 스캔 중
(-1, 8) 좌표 스캔 중
(-1, 7) 좌표 스캔 중
(-1, 6) 좌표 스캔 중
(0,7)로 시작하는 blob의 크기는 1
(2, 6) 좌표 스캔 중
2 2 0 0 0 0 0 2 
0 2 2 0 0 0 0 0 
0 0 2 2 0 0 1 0 
0 0 0 2 0 1 0 1 
0 0 2 0 0 0 1 0 
0 0 0 0 0 0 1 0 
0 0 1 0 0 0 0 1 
1 1 0 0 0 0 1 0 

2 2 0 0 0 0 0 2 
0 2 2 0 0 0 0 0 
0 0 2 2 0 0 2 0 
0 0 0 2 0 1 0 1 
0 0 2 0 0 0 1 0 
0 0 0 0 0 0 1 0 
0 0 1 0 0 0 0 1 
1 1 0 0 0 0 1 0 

(2, 5) 좌표 스캔 중
(3, 5) 좌표 스캔 중
2 2 0 0 0 0 0 2 
0 2 2 0 0 0 0 0 
0 0 2 2 0 0 2 0 
0 0 0 2 0 1 0 1 
0 0 2 0 0 0 1 0 
0 0 0 0 0 0 1 0 
0 0 1 0 0 0 0 1 
1 1 0 0 0 0 1 0 

2 2 0 0 0 0 0 2 
0 2 2 0 0 0 0 0 
0 0 2 2 0 0 2 0 
0 0 0 2 0 2 0 1 
0 0 2 0 0 0 1 0 
0 0 0 0 0 0 1 0 
0 0 1 0 0 0 0 1 
1 1 0 0 0 0 1 0 

(3, 4) 좌표 스캔 중
(4, 4) 좌표 스캔 중
(4, 5) 좌표 스캔 중
(4, 6) 좌표 스캔 중
2 2 0 0 0 0 0 2 
0 2 2 0 0 0 0 0 
0 0 2 2 0 0 2 0 
0 0 0 2 0 2 0 1 
0 0 2 0 0 0 1 0 
0 0 0 0 0 0 1 0 
0 0 1 0 0 0 0 1 
1 1 0 0 0 0 1 0 

2 2 0 0 0 0 0 2 
0 2 2 0 0 0 0 0 
0 0 2 2 0 0 2 0 
0 0 0 2 0 2 0 1 
0 0 2 0 0 0 2 0 
0 0 0 0 0 0 1 0 
0 0 1 0 0 0 0 1 
1 1 0 0 0 0 1 0 

(4, 5) 좌표 스캔 중
(5, 5) 좌표 스캔 중
(5, 6) 좌표 스캔 중
2 2 0 0 0 0 0 2 
0 2 2 0 0 0 0 0 
0 0 2 2 0 0 2 0 
0 0 0 2 0 2 0 1 
0 0 2 0 0 0 2 0 
0 0 0 0 0 0 1 0 
0 0 1 0 0 0 0 1 
1 1 0 0 0 0 1 0 

2 2 0 0 0 0 0 2 
0 2 2 0 0 0 0 0 
0 0 2 2 0 0 2 0 
0 0 0 2 0 2 0 1 
0 0 2 0 0 0 2 0 
0 0 0 0 0 0 2 0 
0 0 1 0 0 0 0 1 
1 1 0 0 0 0 1 0 

(5, 5) 좌표 스캔 중
(6, 5) 좌표 스캔 중
(6, 6) 좌표 스캔 중
(6, 7) 좌표 스캔 중
2 2 0 0 0 0 0 2 
0 2 2 0 0 0 0 0 
0 0 2 2 0 0 2 0 
0 0 0 2 0 2 0 1 
0 0 2 0 0 0 2 0 
0 0 0 0 0 0 2 0 
0 0 1 0 0 0 0 1 
1 1 0 0 0 0 1 0 

2 2 0 0 0 0 0 2 
0 2 2 0 0 0 0 0 
0 0 2 2 0 0 2 0 
0 0 0 2 0 2 0 1 
0 0 2 0 0 0 2 0 
0 0 0 0 0 0 2 0 
0 0 1 0 0 0 0 2 
1 1 0 0 0 0 1 0 

(6, 6) 좌표 스캔 중
(7, 6) 좌표 스캔 중
2 2 0 0 0 0 0 2 
0 2 2 0 0 0 0 0 
0 0 2 2 0 0 2 0 
0 0 0 2 0 2 0 1 
0 0 2 0 0 0 2 0 
0 0 0 0 0 0 2 0 
0 0 1 0 0 0 0 2 
1 1 0 0 0 0 1 0 

2 2 0 0 0 0 0 2 
0 2 2 0 0 0 0 0 
0 0 2 2 0 0 2 0 
0 0 0 2 0 2 0 1 
0 0 2 0 0 0 2 0 
0 0 0 0 0 0 2 0 
0 0 1 0 0 0 0 2 
1 1 0 0 0 0 2 0 

(7, 5) 좌표 스캔 중
(8, 5) 좌표 스캔 중
(8, 6) 좌표 스캔 중
(8, 7) 좌표 스캔 중
(7, 7) 좌표 스캔 중
(6, 7) 좌표 스캔 중
(6, 6) 좌표 스캔 중
(6, 5) 좌표 스캔 중
(7, 7) 좌표 스캔 중
(7, 8) 좌표 스캔 중
(6, 8) 좌표 스캔 중
(5, 8) 좌표 스캔 중
(5, 7) 좌표 스캔 중
(5, 6) 좌표 스캔 중
(5, 7) 좌표 스캔 중
(4, 7) 좌표 스캔 중
(4, 6) 좌표 스캔 중
(4, 5) 좌표 스캔 중
(5, 7) 좌표 스캔 중
(4, 7) 좌표 스캔 중
(3, 7) 좌표 스캔 중
2 2 0 0 0 0 0 2 
0 2 2 0 0 0 0 0 
0 0 2 2 0 0 2 0 
0 0 0 2 0 2 0 1 
0 0 2 0 0 0 2 0 
0 0 0 0 0 0 2 0 
0 0 1 0 0 0 0 2 
1 1 0 0 0 0 2 0 

2 2 0 0 0 0 0 2 
0 2 2 0 0 0 0 0 
0 0 2 2 0 0 2 0 
0 0 0 2 0 2 0 2 
0 0 2 0 0 0 2 0 
0 0 0 0 0 0 2 0 
0 0 1 0 0 0 0 2 
1 1 0 0 0 0 2 0 

(3, 6) 좌표 스캔 중
(4, 6) 좌표 스캔 중
(4, 7) 좌표 스캔 중
(4, 8) 좌표 스캔 중
(3, 8) 좌표 스캔 중
(2, 8) 좌표 스캔 중
(2, 7) 좌표 스캔 중
(2, 6) 좌표 스캔 중
(3, 6) 좌표 스캔 중
(3, 5) 좌표 스캔 중
(3, 6) 좌표 스캔 중
(2, 6) 좌표 스캔 중
(2, 5) 좌표 스캔 중
(2, 4) 좌표 스캔 중
(3, 6) 좌표 스캔 중
(3, 7) 좌표 스캔 중
(2, 7) 좌표 스캔 중
(1, 7) 좌표 스캔 중
(1, 6) 좌표 스캔 중
(1, 5) 좌표 스캔 중
(2,6)로 시작하는 blob의 크기는 7
(6, 2) 좌표 스캔 중
2 2 0 0 0 0 0 2 
0 2 2 0 0 0 0 0 
0 0 2 2 0 0 2 0 
0 0 0 2 0 2 0 2 
0 0 2 0 0 0 2 0 
0 0 0 0 0 0 2 0 
0 0 1 0 0 0 0 2 
1 1 0 0 0 0 2 0 

2 2 0 0 0 0 0 2 
0 2 2 0 0 0 0 0 
0 0 2 2 0 0 2 0 
0 0 0 2 0 2 0 2 
0 0 2 0 0 0 2 0 
0 0 0 0 0 0 2 0 
0 0 2 0 0 0 0 2 
1 1 0 0 0 0 2 0 

(6, 1) 좌표 스캔 중
(7, 1) 좌표 스캔 중
2 2 0 0 0 0 0 2 
0 2 2 0 0 0 0 0 
0 0 2 2 0 0 2 0 
0 0 0 2 0 2 0 2 
0 0 2 0 0 0 2 0 
0 0 0 0 0 0 2 0 
0 0 2 0 0 0 0 2 
1 1 0 0 0 0 2 0 

2 2 0 0 0 0 0 2 
0 2 2 0 0 0 0 0 
0 0 2 2 0 0 2 0 
0 0 0 2 0 2 0 2 
0 0 2 0 0 0 2 0 
0 0 0 0 0 0 2 0 
0 0 2 0 0 0 0 2 
1 2 0 0 0 0 2 0 

(7, 0) 좌표 스캔 중
2 2 0 0 0 0 0 2 
0 2 2 0 0 0 0 0 
0 0 2 2 0 0 2 0 
0 0 0 2 0 2 0 2 
0 0 2 0 0 0 2 0 
0 0 0 0 0 0 2 0 
0 0 2 0 0 0 0 2 
1 2 0 0 0 0 2 0 

2 2 0 0 0 0 0 2 
0 2 2 0 0 0 0 0 
0 0 2 2 0 0 2 0 
0 0 0 2 0 2 0 2 
0 0 2 0 0 0 2 0 
0 0 0 0 0 0 2 0 
0 0 2 0 0 0 0 2 
2 2 0 0 0 0 2 0 

(7, -1) 좌표 스캔 중
(8, -1) 좌표 스캔 중
(8, 0) 좌표 스캔 중
(8, 1) 좌표 스캔 중
(7, 1) 좌표 스캔 중
(6, 1) 좌표 스캔 중
(6, 0) 좌표 스캔 중
(6, -1) 좌표 스캔 중
(8, 0) 좌표 스캔 중
(8, 1) 좌표 스캔 중
(8, 2) 좌표 스캔 중
(7, 2) 좌표 스캔 중
(6, 2) 좌표 스캔 중
(6, 1) 좌표 스캔 중
(6, 0) 좌표 스캔 중
(7, 2) 좌표 스캔 중
(7, 3) 좌표 스캔 중
(6, 3) 좌표 스캔 중
(5, 3) 좌표 스캔 중
(5, 2) 좌표 스캔 중
(5, 1) 좌표 스캔 중
(6,2)로 시작하는 blob의 크기는 3
2 2 0 0 0 0 0 2 
0 2 2 0 0 0 0 0 
0 0 2 2 0 0 2 0 
0 0 0 2 0 2 0 2 
0 0 2 0 0 0 2 0 
0 0 0 0 0 0 2 0 
0 0 2 0 0 0 0 2 
2 2 0 0 0 0 2 0 

최종 blob의 개수는 4
크기가 8
크기가 1
크기가 7
크기가 3

재귀함수는 너무 어려워 ㅠㅠ

저작자표시 비영리 변경금지

'컴퓨터 공부방 > 알고리즘' 카테고리의 다른 글

알고리즘 정렬 시간복잡도 정리 (0)	2019.09.14
멱집합 Powerset 알고리즘 (재귀함수 응용) with JAVA (0)	2019.09.13
N-Queens 여왕 알고리즘 with JAVA (0)	2019.09.12
미로찾기 알고리즘 (재귀함수 응용문제) JAVA (1)	2019.09.10
재귀함수 (Recursion) 개념 및 특성 (0)	2019.09.08

공지사항

최근에 올라온 글

최근에 달린 댓글

Total

Today

Yesterday

링크

TAG more

« 2025/01 »
일	월	화	수	목	금	토
			1	2	3	4
5	6	7	8	9	10	11
12	13	14	15	16	17	18
19	20	21	22	23	24	25
26	27	28	29	30	31

글 보관함

다이제 공부방

티스토리 뷰