Java 미로찾기 - Java milochajgi

Question

개인적으로 재귀함수적인 사고를 할 수 있도록 도와 준 정말 고마운 알고리즘이라고 생각한다.

아무래도 재귀함수적인 사고에 익숙하지 않기 때문에 이런 훈련이 필요하다고 생각은 했다.

재귀함수는 팩토리얼과 같은 간단한 수식 정도만 계산하는 장난감스러운 아이디어라고 생각했는데, 이러한 선입견을 완벽하게 깨부쉈다.

재귀함수 하나만으로도 이렇게 문제를 해결할 수 있다는 데에 감탄사가 절로 나온다.

문제 확인

public class Maze{
	private static int N = 8;
	private static int[][] maze= {
			{0,0,0,0,0,0,0,1},
			{0,1,1,1,0,1,0,1},
			{0,1,0,1,0,0,0,1},
			{0,0,0,1,1,1,0,0},
			{1,0,1,1,0,0,1,1},
			{0,0,0,0,0,1,0,1},
			{1,0,1,1,0,0,0,1},
			{0,0,1,1,1,1,0,0}
	};
    public static boolean findMazePath(int x, int y) {
        //TODO: 구현부
    }
	public static void printMaze() {
        // 2차원 배열 출력 메서드
		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();
	}
}

접근 방법

처음에는 엄두가 나지 않았다. 이런 재귀 문제를 어떻게 풀지?

일단 메서드에서 findMazePath(0,0)을 주고 시작하는 것을 보면 x와 y좌표 0,0에서 시작한다는 사실은 알 수 있다.

그렇다면 그 다음은 어떻게?

일단 사람이 푸는 방식 먼저 확인해 보자.

사람이 푸는 방식

연필로 한 칸 한 칸 긋고 막히는 부분이 있으면 경로를 지우고 새로운 경로를 탐색하지 않을까?

보다 정확한 탐색을 위해 색깔별 볼펜을 사용하여 탐색한 경로를 한 눈에 볼 수 있도록 표시해 보았다.

[경로를 찾을 때까지 반복되는 작업]

1. 방향을 정해서 뚫린 곳부터 일단 탐색한다.

2. 끝 부분에 도달했다면? (X축이나 Y축의 끝이면 갈 데가 없으니까 여기에 도달했다면?)

2-A. 막힌 것이므로 되도랑간다.

2-B. X축과 Y축이 모두 끝부분이라면 출구이므로 도착했으므로 프로그램을 종료한다.

기계가 푸는 방식

문제에서는 배열의 0은 지나다닐 수 있는 통로고 1은 벽이라고 했다.

그런데 탐색을 할 때마다 막힌 경로인지 혹은 탐색 중인지를 표시해두는 것이 좋겠다.

그런 것들을 표시하지 않는다면 분명 다른 위치에서 이미 탐색해서 온 경로를 또 다시 재귀호출하여 무한루프에 빠질 수 있을 테니까!

어떻게 하면 좋을까?

일단 탐색중인 경로를 2라고 하고, 탐색을 다 했는데 막혔다면 3으로 채워나가기로 하였다.

1. 코드를 작성하기에 앞서 재귀함수를 사용해서 해결한다는 것을 명심하자.

(이것은 마치 등 운동을 하는 데 이두근의 개입이 심하게 들어가지 말자고 명심하는 것과 비슷한 이치랄까?)

2. 사람의 눈은 여러 배열들을 한꺼번에 볼 수 있으나 컴퓨터는 배열의 전체를 보고 시작하는 것이 아니다. 단지 하나만의 배열을 확인하면서 찾아다니는 것이다.

(마치 3D 리얼리티 미로게임을 한다고 생각하는 자세로 임해야 한다.)

다음은 초기 배열의 값을 그림으로 표기한 것이다.

재귀함수가 헷갈린다면 이렇게 하나씩 하나씩 디버깅하면서 탐색해 나가는 것이 재귀함수적 사고를 하는 데 도움을 줄 것 같다고 생각해서 작성해 보았다.

실제로도 이렇게 작성하면서 보니 좀 재귀함수적인 사고에 대해 무의식이 이해하고 있다는 생각이 든다.

프로그램 코드를 완성하고 디버깅 과정을 손수 적었다.

개념은 참 말로 이해하기는 쉬운데, 사람이 대입하면서 풀어가다 보면 규칙은 알겠지만 매번 재귀적으로 새로운 일을 벌이고 어떻게 다른 일을 시작해야 하는지 작업을 번번이 하다 보니 부담이 되는 것 같다.

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;
	private static final int WALL_COLOR = 1;
	private static final int BLOCKED_COLOR = 2;
	private static final int PATH_COLOR = 3;
	
	public static boolean findMazePath(int x, int y) {
		if(x<0||y<0||x>=N||y>=N) {
			//좌표의 유효한 범위 밖이면 false를 반환한다.
			return false;
		}
		else if(maze[x][y] != PATHWAY_COLOR) {
			//wall, blocked, path color의 경우에는 false를 호출한다.
			return false;
		}
		else if(x==N-1 && y==N-1) {
			//출구의 경우 (배열의 끝 of 끝)
			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;
			}
			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();
	}
}