[알고리즘] 순환(Recursion) 04 - 미로찾기

순환(Recursion) 응용편 : 미로찾기

인프론 강의를 보면서 연습하고 기록하고 있습니다

미로탐색 아이디어 (출구까지의 경로 유무)

현재위치에서 출구까지 가는 경로가 있으려면
1) 현재 위치가 출구?
2) 이웃한 셀 중 하나에서 현재 위치를 지나지 않고 출구까지 가는 경로가 있나?

boolean findPath(x,y) {
	if(x,y) is the exit {
		return true;
	}else {
		mark (x,y) as a visited cell;
		for each neighbouring cell (x`,y`) of (x,y) do
			if(x`,y`) is on the pathway and not visited{
				if(findpath(x`,y`)) {
					return true;
				}
			}
		return false;
	}
}

boolean findPath(x,y) {
	if(x,y) is either on the wall or a visited cell {
		return false;
	}else if(x,y) is the exit {
		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;
	}
}

매개변수의 명시화 : 순차탐색 다른 버전

public class Test {
	private static int N = 8; //미로범위
	private static int[][] maze = {
			{0, 0, 0, 0, 0, 0, 0, 1},
			{0, 1, 1, 1, 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 = 0;
	private static final int WALL = 1;
	private static final int BLOCKED = 2; //꽝
	private static final int PATH = 3; //방문했고 아직 꽝인지 모름

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

	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){ //방문했거나, 꽝, 또는 벽이면 검사할 필요 없지
			return false;
		}else if(x==N-1 && y==N-1){ //출구 일때
			maze[x][y] = PATH;
			return true;
		}else {
			maze[x][y] = PATH;
			if(findMazePath(x-1, y) || findMazePath(x, y+1) ||
					findMazePath(x+1, y) || findMazePath(x, y-1)) {
				return true;
			}
			maze[x][y] = BLOCKED; //꽝
			return false;
		}
	}

	public static void printMaze() {
		System.out.println("---------------------------------");
		for (int i = 0; i < maze.length; i++) {
			for (int j = 0; j < maze.length; j++) {
				System.out.print(maze[i][j] +" ");
			}
			System.out.println();
		}
		System.out.println("---------------------------------");
	}

// 미로
---------------------------------
0 0 0 0 0 0 0 1
0 1 1 1 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
---------------------------------

// 미로찾기 진행 후
---------------------------------
3 2 2 2 2 2 2 1
3 1 1 1 1 1 2 1
3 2 2 1 2 2 2 1
3 1 2 2 1 1 2 2
3 1 1 1 2 2 1 1
3 1 3 3 3 1 2 1
3 3 3 1 3 3 3 1
0 1 1 1 0 1 3 3
---------------------------------