재귀 함수 (3)

미로찾기

현재 위치에서 출구까지 가는 경로가 있으려면

1. 현재 위치가 출구이거나 혹은
2. 이웃한 셀들 중 하나에서 현재 위치를 지나지 않고 출구까지 가는 경로가 있거나

boolean findPath(x,y)
	if(x,y) is the exit
		return true;
	else 
		for each neighbouring cell (x', y') of (x,y) do
			if(x',y') is on the pathway
				if(findPath(x',y')
					return true;
			return false

미로찾기는 답이 Yes or No인 문제이다.

boolean findPath(x,y)
	if(x,y) is either on the wall or a visited cell
		return false;
	else if (x,y) as a visited cell;
		return true;
	else
		mark(x,y) as a visited cell;
		for each neighbouring cell (x',y') of (x,y) do
			if findPath(x', y')
				return true;
		return false;

package CodeTest;

public class Maze {
	
	private static int N = 8;
	private static int[][] maze={
		{0,0,0,0,0,0,0,1},
		{0,1,1,0,1,1,0,1},
		{0,0,0,1,0,0,0,1},
		{0,1,0,0,1,1,0,0},
		{0,1,1,1,0,0,1,1},
		{0,1,0,0,0,1,0,1},
		{0,0,0,1,0,0,0,1},
		{0,1,1,1,0,1,0,0},
	};
	
	private static final int PATHWAY_COLOR = 0; //white
	private static final int WALL_COLOR = 1; //blue
	private static final int BLOCKED_COLOR = 2; //red
	private static final int PATH_COLOR = 3; //green
	//PATH_COLOR : visited이며 아직 출구로 가는 경로가 될 가능성이 있는 cell
	//BLOCKED_COLOR : visited이며 출구까지 경로상에 있지 않음이 밝혀진 cell
	
	public static boolean findMazePath(int x, int y){
		if(x<0 || y<0 || x>=N || y>=N) //범위 벗어남 
			return false;
		else if(maze[x][y] != PATHWAY_COLOR) //벽이거나, 이미 갔던 경로이면
			return false;
		else if(x==N-1 && y==N-1){ //출구 
			maze[x][y] = PATH_COLOR;
			return true;
		}else{
			maze[x][y] = PATH_COLOR;
			if(findMazePath(x-1, y) || findMazePath(x, y+1) || findMazePath(x+1, y) || findMazePath(x, y-1)){
				return true; //상하좌우 위치를 recursion을 한다.
			}
			maze[x][y] = BLOCKED_COLOR; //dead end
			return false;
		}
	}
	
	public static void printMaze(){
		for(int i=0; i<maze.length; i++){
			for(int j=0; j<maze[i].length; j++){
				System.out.print(maze[i][j] + " ");
			}
			System.out.println();
		}
		System.out.println();
	}

	public static void main(String[] args) {
	
		printMaze();
		findMazePath(0,0);
		printMaze();

	}

}

PATH_COLOR : visited이며 아직 출구로 가는 경로가 될 가능성이 있는 cell BLOCKED_COLOR : visited이며 출구까지 경로상에 있지 않음이 밝혀진 cell

• 움직인 경로

Counting Cells in a Blob

Binary 이미지

각 픽셀은 backgroud pixel 이거나 혹은 image pixel

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

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

입력 :

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

출력 :

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

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

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

0을 반환한다.

• Recursive Thinking

현재 픽셀이 image color라면

먼저 현재 픽셀을 카운트한다 (count = 1).

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

현재 픽셀에 이웃한 모든 픽셀에 대해서 그 픽셀이 속한 blob의 크기를 카운트하여 카운터에 더해준다.

카운터를 반환한다.

Algorithm for countCells(x,y)
if the pixel (x,y) is outside the grid
	the rwsult is 0;
else if pixel(x,y) is not an image pixel or already counted
	the result is 0;
else
	set the color of the pixel(x,y) to a red color; (red = 이미 카운트 됨)
	the result is 1 plus the number of cells in each piece of the blob that includes
		a nearest neighbour;

package CodeTest;

public class CountingCellsInABlob {
	
	private static int BACKGROUND_COLOR = 0;
	private static int IMAGE_COLOR = 1;
	private static int ALREADY_COUNTED = 2;
	
	private static int N = 8;
	private static int[][] grid = {
		{1,0,0,0,0,0,0,1},
		{0,1,1,0,0,1,0,0},
		{0,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},
	};
	
	
	public static int countCells(int x, int y){
		if(x<0 || x>=N || y<0 || y>=N)
			return 0;
		else if(grid[x][y] != IMAGE_COLOR)
			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);  
		}
	}
	
	public static void printCell(){
		
		for(int i=0; i<N; i++){
			for(int j=0; j<N; j++){
				System.out.print(grid[i][j] + " ");
			}
			System.out.println();
		}
	}

	public static void main(String[] args) {
		printCell();
		System.out.println();
		System.out.println("좌표에 속한 Blob의 크기 :  "+countCells(5, 3));
		System.out.println();
		printCell();

	}

}

N-Queens Problem

백트래킹이라는 방법을 사용해 풀수 있다.

상태공간 트리

상태공간트리란 찾는 해를 포함하는 트리.

즉 해가 존재한다면 그것은 반드시 이 트리의 어떤 한 노드에 해당한다.

따라서 이 트리를 체계적으로 탐색하면 해를 구할 수 있음

상태공간 트리의 모든 노드를 탐색해야 하는 것은 아니다.

되추적 기법(Backtracking)

상태 공간 트리를 깊이 우선 방식으로 탐색하여 해를 찾는 알고리즘을 말한다.

• recursion
• stack

위 두 방법으로 백트래킹을 구현이 가능하다.

• Design Recursion

return-type queens(argument){
	if non-promising(꽝)
		report failure and return;
	else if success
		report answer and return;
	else
		visit children recursively;
}

argument : 내가 현재 트리의 어떤 노드에 있는지 지정

int[] cols = new int [N+1];
return-type queens(int level){
	if non-promising
		report failure and return;
	else if success
		report answer and return;
	else
		visit children recursively;
}

매개변수 level은 현재 노드의 레벨을 표현한다.

1번째에서 level번째 말이 어디에 놓였는지는 전역변수 배열 cols로 표현

cols[i] = j는 i번 말이 (i행, j열)에 놓여있음을 의미한다.

cols[1] : 1번말이 놓인 열번호

cols[2] : 2번말이 놓인 열번호

cols[3] : 3번말이 놓인 열번호

cols[4] : 4번말이 놓인 열번호

...

cols[level] : level번말이 놓인 열번호

1~level 까지의 노드가 있다.

int[] cols = new int[N+1];
boolean queens(int level){
	if non-promising
		report failure and return;
	else if success
		report answer and return;
	else
		visit children recursively;
}

return-type은 일단 boolean으로 둔다.

즉, 성공이냐 실패냐를 반환한다.

int[] cols = new int[N+1];
boolean queens(int level){
	if (!promising(level))
		return false;	
	else if success
		report answer and return;
	else
		visit children recursively;
}

노드가 어떤 경우에 non-promising일까?

int[] cols = new int[N+1];
boolean queens(int level){
	if (!promising(level))
		return false;	
	else if (level == N)
		return true;
	else
		visit children recursively;
}

promising 테스트를 통과했다는 가정하에 level == N 이면 모든 말이 놓였다는 의미이고 따라서 성공이다.

int[] cols = new int[N+1];
boolean queens(int level){
	if (!promising(level))
		return false;	
	else if (level == N)
		return true;
	for(int i=1; i<=N; i++){
		cols[level+1] = i;
		if(queens(level+1))
			return true;
	}
	return false;
}

level + 1 번째 말을 각각의 열에 놓은 후 recursion을 호출한다.

• Promising Test

boolean promising(int level){
	for(int i=1; i<level; i++){
		if(cols[i] == cols[level]) 
			return false; //같은 열에 놓여있는지 검사
		else if on the same diagonal
			return false; //같은 대각선에 놓여있는지 검사
		}
		return true;
}

대각선 검사

대각선이 두 방향이기 때문에 절대값을 씌운다.

level - i 랑 같다면 대각선에 놓여져있는 것이다.

boolean promising(int level){
	for(int i=1; i<level; i++){
		if(cols[i] == cols[level]) 
			return false; //같은 열에 놓여있는지 검사
		else if (level-i == Math.abs(cols[level]-cols[i])
			return false; //같은 대각선에 놓여있는지 검사
		}
		return true;
}

(x,y) (행,열)좌표로 있을 때

현재행(x)- 검사행(x) == |현재열(y) - 검사열(y)|

값이 같으면 대각선에 위치하는 것이다.

즉 행의 차와 열의 차가 같으면 대각선에 위치

package Algorithm2;

public class NQueen {
	
	public static int N = 4;
	public static int[] cols = new int[N+1]; //정답을 저장
	
	public static boolean queens(int level){
		if(!promising(level)) //같은열 , 대각선 검사
			return false;
		else if(level == N) { //최대 크기인 N에 위치한다면 검사는 종료 
			print();
			return true;
		}
		for(int i=1; i<=N; i++){
			cols[level+1] = i;
			if(queens(level+1)) //자식 노드 검사
				return true;
		}
		return false;
	}
	
	public static boolean promising(int level){
		for(int i=1; i<level; i++){
			if(cols[i] == cols[level] || level-i == Math.abs(cols[level]-cols[i])){
				return false; //같은열 || 대각선 검사
				//행의 차와 열의 차가 같으면 대각선에 위치
			}
		}
		return true;
	}
	
	public static void print(){
		for(int i=1; i<=N; i++){
			System.out.print(cols[i] + " ");
		}
		System.out.println();
	}
	public static void main(String[] args) {
		queens(0);

	}

}