Java Recursion example

Java에서 재귀호출(Recursion)을 이용한 길찾기 예

2차원 정수배열의 한 위치에서 해당 원소와 인접한 8개의 원소들을 검사하여 값이 0 으로 설정된 경우를 모두 찾아내는 재귀호출의 예이다

한개의 원소와 인접한 원소는 모두 8개(좌우상하+4개의 모서리)이므로 8개의 원소들을 검사하여 그 중에서 0으로 설정된 원소의 주변을 다시 검사하는 작업을 반복적으로 수행한다. 0으로 설정되지 않은 원소를 만나면 재귀호출을 하지 않으면 된다

public class RecursionTest {

	static int[][] arr;
	static {
		arr = new int[5][5];
		arr[0][0]=0;  arr[0][1]=1;  arr[0][2]=1;  arr[0][3]=0;  arr[0][4]=1;
		arr[1][0]=1;  arr[1][1]=0;  arr[1][2]=1;  arr[1][3]=1;  arr[1][4]=0;
		arr[2][0]=1;  arr[2][1]=1;  arr[2][2]=0;  arr[2][3]=0;  arr[2][4]=0;
		arr[3][0]=1;  arr[3][1]=0;  arr[3][2]=1;  arr[3][3]=1;  arr[3][4]=1;
		arr[4][0]=0;  arr[4][1]=1;  arr[4][2]=0;  arr[4][3]=1;  arr[4][4]=1;
	}
	/* { 0, 1, 1, 0, 1 },
	 * { 1, 0, 1, 1, 0 },
	 * { 1, 1, 0, 0, 0 },
	 * { 1, 0, 1, 1, 1 },
	 * { 0, 1, 1, 1, 1 }
	 */

	public static void main(String[] args) {
		findPath(0,0);
 	}

	static void findPath(int r, int c ) {
		if(arr[r][c]==0) {
			System.out.printf("[%d][%d] ", r,c);
			arr[r][c] = 1;

			if(c+1 < arr[r].length) { //우측검사
				findPath(r,c+1);
			}
			if(r+1<arr.length && c+1 <arr[r+1].length) { //우측 아래 대각선 검사
				findPath(r+1,c+1);
			}
			if(r+1<arr.length ) { // 아래검사
				findPath(r+1,c);
			}
			if(r+1<arr.length && c-1>=0) { //좌측아래 대각선 검사
				findPath(r+1,c-1);
			}
			if(c-1>=0) { // 좌측검사
				findPath(r,c-1);
			}
			if(r-1>=0 && c-1>=0) { //좌측 위 대각선 검사
				findPath(r-1,c-1);
			}
			if(r-1>=0){ // 위 검사
				findPath(r-1,c);
			}
			if(r-1>=0 && c+1<arr[r-1].length){ // 위 오른쪽 대각선 검사
				findPath(r-1,c+1);
			}
		}
	}
	
}