[Algorithm/Java] DFS(깊이 우선 탐색)

DFS(Depth-First Search) : 깊이 우선 탐색

• 그래프 완전 탐색 : 모든 노드를 방문하고자 할때, 이 방법을 선택한다.
• 그래프의 시작 노드에서 출발하여 탐색할 한 쪽 분기를 정해서 최대깊이까지 탐색을 마친 후,
  다른쪽 분기로 이동하여 다시 탐색을 수행하는 알고리즘이다.
• 재귀함수 또는 Stack 자료구조를 이용한다.
• 재귀함수를 이용하므로 stack overflow에 유의해야 한다.

스택 오버플로우(stack overflow)는 지정한 스택 메모리 사이즈보다 더 많은 스택 메모리를 사용하게 되어 에러가 발생하는 상황을 일컫는다.

---

1. 시간복잡도

(노드 수: N, 에지 수 E)

인접 리스트

• 노드의 개수가 많고, 간선 수가 적을 때 유리하다.

인접 행렬

• 노드의 개수가 적고, 간선 수가 많을 때 유리하다.

	인접 리스트	인접 행렬
특정 간선 검색	O(degree(N) : 해당 노드의 차수	O(1)
정점의 차수 계산	O(degree(N))	O(N)
전체 노드 탐색	O(E)	O(N^2)
메모리	N+E	N^2

 

---

2. DFS 핵심 이론

1) 방문여부 확인용 배열

1	2	3	4	5	6
T	F	F	F	F	F

DFS는 한번 방문한 노드를 다시 방문하면 안되므로 노드 방문 여부를 체크할 배열이 필요하다.

   ( 이부분이 제대로 되지 않으면 , 재귀함수로 인해 무한루프에 빠질 수 있으니 조심해야 한다. )

예를들어 1~6의 노드를 가진 그래프가 있으면, `boolean[] arr = new boolean[7];` 으로 배열을 만들어 준다.

   ( 0번 인덱스는 사용하지 않는다. )

해당 노드를 방문하면 해당 인덱스의 값을 TRUE로 바꿔준다.

2) 원본 그래프 -> 자료구조 초기화(인접리스트)

1. 시작할 노드를 정한다.
2. 각 노드에서 갈수있는 다른 노드를 확인 후 인접리스트로 초기화 한다.
3. 시작점을 정했기 때문에 시작점의 방문배열을 T로바꿔주고, 스택에 시작점을 더한다.

3) 스택(재귀함수)에서 꺼낸 노드의 인접노드를 스택에 삽입

1. 맨 처음에 넣었던 시작노드 1을 스택에서 pop 한다. ( pop 할때, 해당 값의 방문배열은 T로 변경 )
2. 1의 인접노드 2,3을 스택에 삽입한다.
3. 이 과정을 스택이 비워질 때까지 반복한다.

4) 반복

(편의를 위해 pop() 괄호 안에 값을 넣도록 하겠다.)

1. 위에서 1이 pop되고, 2,3이 스택에 들어있는 상황이다.
2. pop(3) -> 3의 방문배열 True -> 3의 인접노드 push(4)
3. pop(4) -> 4의 방문배열 True -> 4의 인접노드 push(6)
4. pop(6) -> 6의 방문배열 True -> 6은 인접노드가 없기 때문에 push할 노드는 없다.
5. pop(2) -> 2의 인접노드는 5,6이지만 6의 방문배열은 True 이므로 push(5)만 할수 있다.
6. pop(5) -> 5의 방문배열 True
7. stack.isEmpty() == true

마지막으로 pop(5)를 하고 나니, 스택이 비워졌다. -> 반복 종료

결과적으로 탐색 순서는 [ 1 - 3 - 4 - 6 - 2 - 5 ]이다.

---

3. 구현

 

1) 인접리스트 초기화

    static boolean[] visited = new boolean[7]; //방문 배열
    static ArrayList<Integer>[] A = new ArrayList[7];//ArrayList타입 배열
    static ArrayList<Integer> procedure = new ArrayList<>(); //탐색 순서 list

    public static void main(String[] args){
    
 	//배열의 각 요소마다 ArrayList를 가진다.
        for(int i=1;i<=6;i++) {
            A[i] = new ArrayList<>();
        }
        A[1].add(2);
        A[1].add(3);
        A[2].add(5);
        A[2].add(6);
        A[3].add(4);
        A[4].add(6);
        
        //1번노드에서 DFS 실행
        DFS(1);

        System.out.println(procedure.toString()); 
        // [1, 3, 4, 6, 2, 5] (스택)
        // [1, 2, 6, 5, 3, 4] (재귀)
        // 인접리스트에 들어있는 값의 순서에 따라 탐색 순서가 달라질 수 있으나, 두가지 경우 모두 DFS가 맞다.
    }

2) 구현 1 (Stack 이용)

public static void DFS(int v){
    Stack<Integer> stack = new Stack<>();

    stack.push(v);;
    
    while(!stack.isEmpty()){
        int cur = stack.pop();
        visited[cur] = true;
        procedure.add(cur);

        //해당 노드의 인접리스트를 검사하며, visited가 false인 경우에만 stack.push
        for (int i : A[cur]) {
            if(!visited[i]){
                stack.push(i);
            }
        }
    }
}

3) 구현 2 ( 재귀함수 이용 )

   static void DFS(int v){
        //방문배열이 true면 return
        if(visited[v]) return;

        //v 노드에 방문했으므로, 해당 방문배열을 true로 바꿔주고, 탐색순서 리스트에 추가해줌
        visited[v] = true;
        procedure.add(v);

        //해당노드의 ArrayList(인접노드)를 모두 돌며 방문배열이 false인 경우에
        for(int i : A[v]){
            if(!visited[i]){
                DFS(i); //해당 노드에 대해서 DFS를 다시 실행한다.
            }
        }
    }

---

(참고) Do it! 알고리즘 코딩 테스트 자바 편
http://www.yes24.com/Product/Goods/108571508