[알고리즘] Recursion의 응용 - 미로 찾기

인프런 무료 강의 권오흠교수님 '영리한 프로그래밍을 위한 알고리즘 강좌' 보면서 공부한 내용입니다.
부족한 내용이나 잘못된 내용은 댓글남겨주시면 감사하겠습니다!

출처 : https://inf.run/iezc

 

저번시간까지 학습한 순환함수를 응용하여 미로찾기를 해보았다.

 

현재 위치에서 출구까지 가는 경로가 있으려면
1) 현재 위치가 출구이거나 혹은
2) 이웃한 셀들 중 하나에서 현재 위치를 지나지 않고 출구까지 가는 경로가 있거나
  
미로 찾기 (Decision Problem)
답이 yes or no인 문제 - 출발점에서 출구까지 가는 경로가 있는지 없는지

 

public static boolean findPath(x, y){
		// 현재 위치가 출구 인지 확인
		if(x, y) is the exit
			return true;
		else
			// x, y에 인접한 셀 4개에 대해 for each
			for each neighbouring cell (x', y') of (x, y) do
				// x', y'가 통로가 아닌 경우는 생각할 필요가 없음
				// x', y'가 사람이 다닐 수 있는 통로 일 경우
				if(x', y') is on the pathway
					if findPath(x', y')
						return true; // 통로일 경우 true
			return false;
	}

 

// 무한루프를 최대한 방지하고자 개선한 코드
// 내가 이미 방문한 위치와 그렇지 않는 위치 구분!
	public static boolean findPath(x, y){
		// 현재 위치가 출구 인지 확인
		if(x, y) is the exit
			return true;
		else
			// 현재 위치가 방문한 위치라는 것을 마커로 표기
			mark (x, y) as a visited cell; 
			
			// 그 위치에 인접한 4개의 위치에 대해
			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;
	}

 

// 최종 수정 코드
public static boolean findPath(x, y){
		// 통로가 아니거나 방문한 위치면 바로 종료
		if(x, y) is the either on the wall or a visited cell
			return false;
		
		// x,y가 출구일 경우
		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;
	}

 

개념은 이렇게 알아보고, 실제 코드를 짜보자

/*
 * Recursion의 응용 - 미로 찾기 4-02
 * 
 * Class Maze
 * -> true
 */
package edu.recursion;

public class Recursion04_02 {
	private static int N = 8;
	
	// 통로 : 0, 벽 : 1
	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_COLOUR = 0; // white - 통로
	private static final int WALL_COLOUR = 1;  	// blue - 벽
	private static final int BLOCKED_COLOUR = 2;	// red - 방문했지만 길이 없음
	private static final int PATH_COLOUR = 3;	// green - 방문했지만 아직까진 출구가 있는지 없는지 판단이 안된 셀
	// 방문후 일단 녹색으로 칠하고 갔는데 길이 없으면 주황으로 칠함
	 
	// PATH_COLOR : visited이며 아직 출구로 가는 경로가 될 가능성이 있는 cell
	//BLOCED_COLOR : visited이며 출구까지의 경로상에 있지 않음이 밝혀진 cell

	// 위치 x,y에 대해 출구까지 있는 경로가 있는지 검색하는 셀
	public static boolean findMazePath(int x, int y){
		// 좌표가 유효한 범위인지 0~n-1
		if(x<0 || y<0 || x>=N || y>=N)
			return false; // 유효 범위 아니면 false
		
		// 통로가 아닐 경우 false - green or red or blue
		else if (maze[x][y] != PATHWAY_COLOUR)
			return false; 
		
		// 출구 일 경우
		else if (x==N-1 && y==N-1) {
			// 방문한 위치이므로 녹색으로 칠하고 true리턴
			maze[x][y] = PATH_COLOUR;
			return true;
		}
		
		else {
			// 방문 했으므로 일단 녹색으로 칠함
			maze[x][y] = PATH_COLOUR;
			
			// 인접한 4개에 대해서 다시 함수 실행
			if(findMazePath(x-1, y) || findMazePath(x, y+1)
					|| findMazePath(x+1, y) || findMazePath(x, y-1)){
				return true;
			}
			maze[x][y] = BLOCKED_COLOUR; // dead end
			return false;
		}
	}
	
	public static void main(String[] args) {
		boolean result = findMazePath(0, 0); // 입구
		System.out.println(result);
	}
}