- 모든 순환함수는 반복문(iteration)으로 변경 가능하다.
- 그 역도 성립함. 즉 모든 반복문은 recursion으로 표현 가능하다.
- 순환함수는 복잡한 알고리즘을 단순하고 알기쉽게 표현하는 것을 가능하게 한다.
- 하지만 함수 호출에 따른 오버헤드가 있다.(매개변수 전달, 액티베이션 프레임 생성 등)
- 적어도 하나의 base case, 즉 순환되지 않고 종료되는 case가 있어야 한다.
- 모든 case는 결국 base case로 수렴해야 한다.
연습
미로찾기
입구는 (0,0)이고 출구는 (n-1, n-1)일때 입구에서 출구까지 도착하는 경우의 수를 찾아보자
현재 위치에서 출구까지 가는 경로가 있으려면
- 현재 위치가 출구이거나 혹은
- 이웃한 셀들 중 하나에서 현재 위치를 지나지 않고 출구까지 가는 경우가 있거나
둘 중 하나이다.
우선 답이 yes 인지 no 인지 경로가 있는지 없는지 생각해보자
boolean findPath(x, y) { // 현재 좌표의 x,y 를 파라미터로 넘긴다.
if (x, y) is the exit { // 현재 위치가 출구라면 true를 리턴한다.
return true;
} else {
for each neighbouring cell(x', y') of (x, y) do { // (x', y') 이웃한 이웃셀 최대 4개
if (x', y') is on the pathway { // 벽이 아니라면
if findPath(x', y') {
return true;
}
}
}
return false;
}
}
간략하게 생각해보면 위와 같이 생각해볼 수 있다. 위에 코드가 무한루프에 빠지는지 반드시 확인해봐야 한다.
이건 무한루프에 빠질 수 있다. (x',y') 입장에서 (x, y)는 다시 인접한 셀이된다. 그래서 무한하게 양쪽 셀을 반복하는 경우가 발생할 수 있다.
그렇기 때문에 내가 방문했던 적이 있는 셀인지 아닌지 확인하는 코드가 더 들어가야 한다.
boolean findPath(x, y) { // 현재 좌표의 x,y 를 파라미터로 넘긴다.
if (x, y) is the exit { // 현재 위치가 출구라면 true를 리턴한다.
return true;
} else {
mark (x, y) as a visited cell; // 방문했다고 표시한다.
for each neighbouring cell(x', y') of (x, y) do { // (x', y') 이웃한 이웃셀 최대 4개
if (x', y') is on the pathway and not visited { // 벽이 아니고 방문한 적이 없는 경우
if findPath(x', y') {
return true;
}
}
}
return false;
}
}
자바코드로 풀이해보자
public static boolean findMazePath(int x, int y) {
if (x < 0 || y < 0 || x >= N || y >= N) { // x,y가 범위를 벗어나는 경우
return false;
} else if (maze[x][y] != PATHWAY_COLOUR) { // 길이 아닌 경우
return false;
} else if (x == N-1 && y == N-1) { // 도착지점에 도착한 경우
maze[x][y] = PATH_COLOUR;
return true;
} else {
maze[x][y] = PATH_COLOUR; // 방문한 곳으로 변경한다.
if (findMazePath(x-1, y) || findMazePath(x, y+1)
|| findMazePath(x+1, y) || findMazePath(x, y-1)) {
return true;
}
maze[x][y] = BLOCKED_COLOUR;
return false;
}
}'자료구조&알고리즘' 카테고리의 다른 글
| 시간복잡도 (0) | 2023.09.19 |
|---|---|
| Array에서 Index는 왜 0부터 시작할까? (2) | 2023.09.15 |
| List 와 Set (1) | 2023.09.12 |
| Array List 와 Linked List (1) | 2023.09.08 |
| Array 와 List 의 차이 (1) | 2023.09.08 |
