[Algorithm] 완전탐색 - DFS

DFS 이란 ?

Depth-First-Search의 약어로, 깊이를 우선적으로 탐색하는 알고리즘이다.

 

그래프 알고리즘에서 기초가 되는 탐색 방식이다.

---

DFS 특징 ?

DFS의 특징 몇 가지를 알아보자.

 

• 문제의 유형에 따라 데이터 저장 방법이 인접 행렬과 인접리스트로 나뉜다.
• 문제의 유형에 따라 데이터의 접근 방법이 달라진다.
• 최대한 깊숙한 곳부터 먼저 탐색을 진행한다.
• 스택의 자료구조를 이용하거나 재귀를 통해 구현한다.
• 백트래킹, 단절선 찾기, 단절점 찾기, 위상 정렬, 사이클 찾기에 활용된다.

---

DFS 구현 순서 ?

구조상 Stack Overflow에 주의하며, 구현 순서를 알아보자.

 

1. 시작 노드를 스택에 삽입 후 방문 처리한다
2. 스택의 최상단 노드에 방문하지 않은 인접한 노드 확인한다.
3. 인접한 노드 발견 시 해당 노드 스택에 넣고 방문 처리한다.
4. 인접한 노드를 모두 방문했을 경우 스택에서 최상단 노드를 꺼낸다.
5. 2~3번 동작을 작업이 없을 때까지 반복한다.

---

DFS 그림으로 살펴보기

[ 그래프 정보 ]

               [ 깊이 : ( 2 ), ( 4 ) ]                         [ 깊이 : (( 3 ), ( 5 )), ( 4 )]                            [ 깊이 : (( 5 )), ( 4 ) ]

                  [ 깊이 : ( 4 ) ]                                           [ 깊이 : X ]                                          [ 깊이 : ( 7 ) ]

[ 탐색 완료 ]

방문 순서 : 1 → 2 → 3 → 5 → 4 → 6 → 7

 

방문 종료 순서 : 3 → 4 → 5 → 2 → 1 → 7 → 6

---

DFS 시간복잡도

모든 곳을 탐색해야 하므로 노드의 확인 곧 시간복잡도와 직결된다.

 

문제 유형에 따라 DFS의 시간복잡도를 알아보자.

 

인접행렬 : O(가로 * 세로)

인접리스트 : O(노드 + 간선)

---

소스코드

// DFS 소스코드

public class DFS {

    // DFS 함수 정의
    static void dfs(int node, int[][]graph, boolean[]visited) {
    
        // 현재 노드 방문 처리
        visited[node] = true;
        System.out.print(node+" ");
        
        // 현재 노드와 연결 노드 확인
        for(int idx=0; idx<graph[node].length; idx++) {
            int nextNode = graph[node][idx];
            
            // 인접한 노드가 미방문인 경우
            if(visited[nextNode] != true) 
            	
                // 해당 노드를 재귀적으로 방문
            	dfs(nextNode,graph,visited);
        }
    }

    public static void main(String[] args) {
    
        // 연결 정보 그래프로 표현
        int [][] graph = {{},{2,3,8},{1,7},{1,4,5},{3,5},{3,4},{7},{2,6,8},{1,7}};
        
        // 방문 여부 확인 배열
        boolean [] visited = new boolean[graph.length];

        // DFS 함수 호출
        dfs(1,graph,visited);

        // 탐색 순서 : 1 → 2 → 7 → 6 → 8 → 3 → 4 → 5
    }
}

---

요약

• DFS는 깊이를 우선적으로 탐색하는 알고리즘이다.
• 인접행렬, 인접리스트 두 가지 유형으로 데이터를 저장될 수 있다.
• 구현 시 Stack Overflow를 주의하자.
• 시간복잡도는 O(가로 * 세로) 또는 O(노드 + 간선) 이다.
• 스택의 자료구조와 재귀를 이용하여 구현한다.