DFS

1. 깊이우선탐색(DFS, Depth First Search)

- 해가 존재할 가능성 있으면 계속 전진 탐색

- 스택 구조, 재귀 호출 이용

- 재귀 호출이 이루어질 때마다 위치가 점점 깊게 들어감

- 너무 깊게 들어가면 overflow 발생하므로, 막히면 나아갈 곳이 있는 곳으로 돌아가서 과정 반복, 모든 곳을 방문했을 때 탐색 종료

- 유용 : 사이클 탐지(Cycle Detection), 위상 정렬(Topological Sorting)

- 장점 : 무한히 넓은 트리에 효과적

- 단점 : 목표 노드가 없는 경로에 깊이 빠질 수 있음 <- 깊이 제한

public class AllRoute {
static int n, cnt;
static int[][] a = new int[][] {{1,1,1,0,0},{0,0,1,1,1},{1,1,1,0,1},{1,0,0,0,1},{1,1,1,1,1}};
public static void main(String[] args){

n = 5;
int i, j;
for(i=0 ; i<n ; i++){
for(j=0; j<n; j++){
if(j==n-1)System.out.println(a[i][j]);
else System.out.print(a[i][j]);
}
}

DFS(0, 0);
System.out.println("경로의 개수 = "+ cnt);
}

public static void DFS(int x, int y){
if(x == n-1 && y == n-1){
cnt++;
return;
}

a[x][y] = 0;

if(x > 0 && a[x-1][y] == 1) DFS(x-1, y);
if(x < n-1 && a[x+1][y] == 1) DFS(x+1, y);
if(y > 0 && a[x][y-1] == 1) DFS(x, y-1);
if(y < n-1 && a[x][y+1] == 1) DFS(x, y+1);

a[x][y] = 1;
}
}