봄이네집의 일고리즘 - 4) 미로 찾기

재귀함수로 미로를 찾아봅시다.

오늘은 재귀함수로 미로를 풀어볼 겁니다.

우선 사람이 미로를 탈출하는 법을 쉬운 말로 풀어보죠.

미로에 입장한다.
길이 보이는 곳으로 전진한다.
갈림길이 나온다 - 임의의 방향을 선택한다.
만약 길이 아니라면: 돌아나온다. 다른 길을 선택해본다.
만약 길이라면: 다음 갈림길이 나올때까지 전진,
갈림길이 또 나오면: 위 과정 반복.
출구가 나오면 : 만세!

네, 사람도 미로를 풀 때 반복문을 수행합니다. 미로에 대해 알지 못하는 상황에서는 한정된 단서만을 가지고 최대한 빨리 탈출할 수 있는 방법을 찾아야 합니다. 한정된 단서란 다음과 같습니다.

  • 내가 가본 길인가? 가본 길을 또 탐색할 필요는 없을 것입니다.
  • 벽인가? 벽을 뚫고 지나갈 수는 없겠죠.
  • 출구가 보이는가? 출구가 보이면 얼른 만세를 외쳐야겠죠?

사람의 미로 탈출에서 힌트를 얻어, 이제 컴퓨터가 미로를 탈출할 수 있게끔 재귀함수를 작성해 봅시다.

base case의 설정

간단합니다. 미로의 출구에 도달했다면 더이상 재귀 호출이 일어날 필요가 없겠죠.
만약 좌표(x, y) == “출구” 라면 더 이상 재귀함수는 실행될 필요가 없습니다.

예외적인 경우들

재귀호출이 일어나며 탐색이 수행될 때, 컴퓨터는 현재 위치의 주변 타일들을 검색하게 될 겁니다. 재귀 호출이 반복되며 탐색을 이어나갈 때 컴퓨터가 미로의 범위 바깥을 벗어나지 않도록 예외를 처리해줘야 합니다.

만약 좌표 x나 y가 미로의 크기 N보다 크다면, 함수는 false를 돌려준 후 종료될 것입니다.

가본 길을 또 가면 안 됩니다. 처음 좌표를 입력받았을 때, 컴퓨터로 하여금 이 좌표는 가본 좌표입니다. 라고 입력하게 한 후 함수 안에서 가본 길인지 아닌지를 확인하게 해야 합니다.

만약 좌표 (x, y) == “방문했던 좌표”라면, 함수는 false를 돌려준 후 종료됩니다.

코드 작성

위의 단서들을 바탕으로 코드를 작성해 봅시다. 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

public static boolean findMaze(int x, int y){
	if (maze[x][y] == "EXIT"){
		maze[x][y] = "VISITED";
		return true;
	}
	
	else if(x < 0 || y < 0 ||x >= LIMIT || y >= LIMIT){
		return false;
	}

	else if(maze[x][y] != "UNVISITED PATH"){
		return false;
	}

	else{
		maze[x][y] = "VISITED";
		if (findMaze(x + 1, y) || findMaze(x, y + 1) || findMaze(x - 1, y) || findMaze(x, y - 1)){
			return true;
		}
		maze[x][y] = "BLOCKED"
		return false;
	}
}
해설

첫 세 개의 조건문에서 우리는 지금 컴퓨터가 방문하고 있는 경로가 탐색을 수행하기에 적합한 경로인지를 판별했습니다.

우선 지금 서있는 곳이 출구라면, 더 이상의 탐색을 수행하지 말고 true를 돌려준 후 함수를 끝냅니다.

지금 서 있는 곳이 방문해보지 않은 경로가 아니라면, 어떠한 경우에도 false를 리턴합니다.

입력받은 경로가 0과 같거나 작은, 혹은 미로의 범위를 벗어나는 좌표라면 false를 리턴한 후 함수를 끝냅니다.

else문에 recursive case가 구현되어 있습니다. 위의 세 조건을 모두 충족하는 경로인 경우, 컴퓨터는 이 경로와 인접한 사방의 경로를 모두 함수에 다시 넣고 실행, 경로를 뻗어갈 수 있는지 탐색합니다. 네 군데의 경로 중 단 하나라도 탐색할 수 있는 경로를 갖고있는다고 판단하면 true를 돌려줄 것입니다. 이런 식으로 컴퓨터는 마지막 true를 찾아내 탐색을 끝낼 것인지, 혹은 경로를 끝내 탐색하지 못해 false를 내보내고 탐색을 끝낼 것인지 결정할 수 있습니다.

이번 예제에 사용된 소스 코드는 제 깃헙 리포지토리에 모두 수록되어 있습니다.