[DataStructure&Algorithm] DFS, 깊이 우선 탐색

DFS

---

개념 - DFS란?

DFS란, Depth-First Search의 약자로 깊이 우선 탐색을 의미합니다. 

DFS는 그래프 구조에서 사용하는 알고리즘 중 하나로 루트노드부터 탐색하는 것이 아닌 가장 깊은 곳에 있는 리프(Leaf)노드노드부터 탐색을 진행하는 탐색 알고리즘이다. 루트노드에서 다음 브랜치로 넘어가기 전에 완전하게 탐색하는 방법이다

 

DFS가 진행되는 순서

 

1. 시작 노드 혹은 루트 노드 A에서 시작합니다.

2. 시작 노드 A와 인접한 노드 B를 찾는다. 이때, 방문 여부를 설정한다.

3. A에 인접한 다른 노드가 아닌, 다시 B에서 인접한 노드를 찾는다.

4. 마지막 노드까지 순회했다면, 해당 노드의 상위 노드로 간다

5. 위의 과정을 반복하면서 모든 노드를 순회한다.

---

특징

• 재귀적이다
  • 스스로를 호출하는 순환 알고리즘이다.
• 방문했던 곳을 기록하지 않으면, 무한 루프에 빠진다는 특징이 있다.
• Pre-,In-,Post-Order같은 탐색 알고리즘들이 모두 DFS의 한 종류이다.

---

구현

구현 방법은 반복문과 재귀함수, 2가지가 존재하는데, 여기서는 반복문을 통한 DFS 구현을 알아 볼 것이다.

public static void dfs(int[][] graph,int start_idx){

	// 방문 여부 표시를 위한 boolean형 배열 선언
    boolean[] visited = new boolean[graph.length];

	// DFS는 Stack 자료구조로 구현
    Stack<Integer> s = new Stack<>();
    
    // 루트 노드 정보 삽입
    s.push(start_idx);

    while(!s.isEmpty()){
    	// 현재 노드
        int cur = s.pop();
        
        // 방문하지 않았다면, pop
        if (!visited[cur]) {
            System.out.print(cur + " ");
            
            // 방문 여부 표시
            visited[cur] = true;
            for (int i = graph.length - 1; i >= 1; i--) {  // 역방향으로 했지만, 정방향으로 해도 가능하다.
                
                // 현재 노드에서 방문할 수 있는 노드가 있으면서,
                // 방문하지 않은 노드라면 스택에 push
                if (graph[cur][i] == 1 && !visited[i]) {
                    s.push(i);
                }
            }
        }
    }
}

---

설명

	1	2	3	4
1	0	1	1	1
2	1	0	0	1
3	1	0	0	1
4	1	1	1	0

0은 방문 불가, 1은 방문 가능

 

예를 들어, 1번 노드부터 4번 노드까지 존재한다고 가정하고, 위의 표와같이 방문 여부를 조사해서 2차원의 정수형 배열을 위의 코드에 넣게 되면, 1번 노드가 방문할 수 있는 2, 3, 4를 먼저 스택에 삽입하게 된다.

Stack과 visited 배열

그러면 위의 사진과 같은 스택의 상태가 될 것이다.

 

그다음에 while문을 계속 돌면서 pop을 통해 cur 노드의 값을 다시 불러 오고, 조건문에 맞게, 방문하지 않으면서 해당 노드에서 갈 수 있는 노드들을 재탐사하며 추가적으로 스택에 넣어주게된다. 

 

여기서 알 수 있는 것은, 1번 노드 이후에 4, 3, 2 번 노드가 동일한 레벨이라는 것을 알 수 있다.

하지만 2번 노드 다음에 3번, 4번 노드를 처리하는 것이 아닌, 2번 노드가 갈 수 있는 노드들을 추가해주면서, 2번 노드 밑에 있는 노드들을 우선적으로 처리하는 것을 알 수 있다.

 

노드의 상태

 

그렇다면, 스택에는 4가 추가될 것이다. 그 다음 반복문 loop에서 visited의 4번노드 방문 여부를 1로 설정할 것이고, 다시 3번 노드를 스택에 추가할 것이다.

 

이러한 반복문을 통해서 간단하게 DFS 알고리즘을 구현할 수 있다.

 

여기서는 역방향으로 그래프를 탐색하면서, 2번 노드부터 처리했지만, 정방향으로 한다면 4번노드부터 탐색해서 DFS를 구현하게 될 것이다.

참고

https://gmlwjd9405.github.io/2018/08/14/algorithm-dfs

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