Recursion-2
Recursion의 응용
예제1) 미로 찾기
dicision Problem: yes or no - 출구가 있는지 없는지 확인
현재 위치에서 출구까지 가는 경로가 있으려면 1) 현재 위치가 출구이거나 2) 이웃한 셀들 중 하나에서 현재 위치를 지나지 않고 출구까지 가는 경로가 있어야 한다.
sudo code
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;
x, y가 출구라면 true, 아니라면 방문한 좌표를 표시 후 길이 있거나 방문한 좌표가 아니라면 findPath()함수를 반복.
혹은, 👇
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 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 = 0;
private static final int wall = 1;
private static final int blocked = 2;
private static final int path = 3; // 맞는 길인지 틀린 길인지 체크하는 변수
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) || findMazePaht(x, y-1)) { // 동서남북 방향 모두 체크
return true;
}
maze[x][y] = blocked;
return false;
}
}
public static void main(String[] args) {
printMaze();
findMazePath(0, 0);
printMaze();
}
}
예제2) Counting Cells in a Blob
Binary 이미지, 각 픽셀은 background pixel 이거나 image pixel이다. 서로 연결된 image pixel들의 집합을 blob이라고 부른다. 상화좌우 및 대각선 방향으로도 연결된 것으로 간주된다.
입력: n*n 크기의 2차원 그리드, 하나의 좌표는 (x, y)
출력: 픽셀 (x, y)가 포함된 blob의 크기
sudo code
Algorithm for countCells(x, y)
if the pixel (x, y) is outside the grid
the result is 0;
else if pixel (x, y) is not an image pixel or already counted
the result is 0;
else
set the colour of the pixel (x, y) to a red colour;
the result is 1 plus the number of cells in each piece of the blob
that includes a neares neighbour;
👇자바 코드로 구현
private static int bacground = 0;
private static int image = 0;
private static counted = 2;
public int countCells(int x, int y) {
if (x<0 || x>=N || y<0 || y>=N)
return 0;
else if (grid[x][y] != image)
return 0;
else {
grid[x][y] = counted;
return 1 + countCells(x-1, y+1) + countCells(x-1, y+1)
+ countCells(x+1, y+1) + countCells(x-1, y)
+ countCells(x+1, y) + countCells(x-1, y-1)
+ countCells(x, y-1) + countCells(x+1, y-1);
}
}