DFS

[REFERENCE] https://gmlwjd9405.github.io/2018/08/14/algorithm-dfs.html

1. DFS (깊이 우선 탐색)
루트 노드에서 시작해서 다음 분기로 넘어가기전에 해당 분기를 완벽하게 탐색하는 방법

ex) 미로 탐색 : 한 방향으로 갈 수 있을 떄까지 계속 가다가 길이 막히면, 가장 가까운 갈림길로 돌아와서 다시 다른 방향을 탐색

모든 노드를 방문하고자 하는 경우 DFS를 사용하여 해결한다.
넓게 탐색하기(BFS) 전에, 깊게 탐색하는 방법
검색속도는 BFS보다 느리지만, 좀 더 간단하다.

2. DFS 특징
- 자기 자신을 호출하는 순환 알고리즘의 형태
- 전위 순회를 포함한 다른 형태의 트리 순회는 모두 DFS의 한 종류이다
- 알고리즘을 구현할 때 가장 큰 차이점은, 그래프 탐색의 경우 어떤 노드를 방문했었는지 여부를 반드시 검사 해야 한다는 것

3. DFS의 과정
1) a 노드를 방문한다
    - 방문한 노드는 방문했다고 표시
2) a와 인접한 노드들을 차례로 순회한다
    - a와 인접한 노드가 없다면 종료
3) a와 이웃한 노드 b를 방문했다면, a와 인접한 또 다른 노드를 방문하기 전에 b의 이웃 노드들을 전부 방문
    - b를 시작 정점으로 DFS를 다시 시작
4) b의 분기를 전부 완벽하게 탐색했다면 다시 a에 인접한 정점들 중에서 방문하지 않은 정점을 찾음
    - b의 분기를 전부 완벽하게 탐색한 뒤에야 a의 다른 이웃 노드를 방문할 수 있음
    - 아직 방문이 안 된 정점이 없으면 종료
    - 방문 안 된 정점을 시작 정점으로 DFS를 시작

4. DFS의 구현
- 순환 호출 이용
- 명시적 스택을 사용 (방문한 정점들을 스택에 저장하였다가 다시 꺼내서 작업)
<DFS 의사코드>

void search(Node root) {
        if(root == null) return;    //1. root방문
        visit(root);
        root.visited=true;             //1-1. 방문한 노드를 표시
        
        //2. root노드와 인접한 정점을 모두 방문
        for each (Node n in root.adjacent) {
            if(n.visited==false) {        //방문하지 않은 정점을 찾아서
                search(n);            //root노드와 인접한, 방문하지 않은 정점을 시작으로 DFS시작
            }
        }
   }

<DFS로 노드를 방문해보자>

public class DFS {
    int n=7;
    int arr[][] = {                    //0열을 제외하고, 각 열에 적힌 1들은
            {0,0,0,0,0,0,0,0},        //연결된 노드번호이다
            {0,0,1,1,0,0,0,0},        //예를 들어, 2열은 1, 4, 5 노드와 연결되어있다
            {0,1,0,0,1,1,0,0},
            {0,1,0,0,0,0,0,0},
            {0,0,1,0,0,0,0,1},
            {0,0,1,0,0,0,1,0},
            {0,0,0,0,0,1,0,0},
            {0,0,0,0,1,0,0,0}
            };
    
    int f[] = new int[n+1];
 
    public void search(int i) {
        f[i]=1;                     //방문을 표시
        for(int j=1;j<=n;j++) {
            if(arr[i][j]==1 && f[j]==0) {
                System.out.println((i+"->"+j));
                search(j);
            }
        }
    }
}

[알고리즘] 깊이 우선 탐색(DFS)이란 - Heee's Development Blog