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

그래프 탐색이란?

: 하나의 정점으로부터 시작하여 차례대로 모든 정점들을 한 번씩 방문하는 것
Ex) 특정 도시에서 다른 도시로 갈 수 있는지 없는지, 전자 회로에서 특정 단자와 단자가 서로 연결되어 있는지

 

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

깊이 우선 탐색(DFS)이란?

• 그래프에서 깊은 부분을 우선적으로 탐색하는 알고리즘
• 미로를 탐색할 때 한 방향으로 갈 수 있을 때까지 계속 가다가 더 이상 갈 수 없게 되면 다시 가장 가까운 갈림길로 돌아와서 이곳으로 부터 다른 방향으로 다시 탐색을 진행하는 방법과 유사
  ⇒ 넓게(wide) 탐색하기 전에 깊게(deep) 탐색

 

깊이 우선 탐색(DFS)의 특징

• 자기 자신을 호출하는 순환 알고리즘의 형태
• 전위 순회(Pre-Order Traversals)를 포함한 다른 형태의 트리 순회는 모두 DFS의 한 종류
• 이 알고리즘을 구현할 때 가장 큰 차이점은, 그래프 탐색의 경우 어떤 노드를 방문했었는지 여부를 반드시 검사 해야 한다는 것‼️
  ⇒ 이를 검사하지 않을 경우 : 무한루프에 빠질 위험 ⭕️

 

DFS 동작과정

1. 탐색 시작 노드를 스택에 삽입하고, 방문 처리를 한다.
2. (1) 스택의 최상단 노드에 방문하지 않은 인접 노드가 있으면 -> 인접 노드를 스택에 넣고, 방문처리 한다.
3. (2) 방문하지 않은 노드가 없으면 스택에서 최상단 노드를 꺼낸다.
4. 2번의 과정을 수행할 수 없을 때까지 반복한다.

 

깊이 우선 탐색(DFS)의 구현

1. 재귀 호출

 static StringBuilder sb = new StringBuilder();
 static boolean[][] node = new boolean[n+1][n+1], 
 static boolean[] visited = new boolean[n+1];
 ​
 static void dfs(int v) {
   if(visited[v])
       return;
   sb.append(v + " ");
   for(int i = 1; i <= n; i++)
     if(node[v][i] && !visited[i]) {
       visited[i] = true;
       dfs(i);
     }
 }

 

2. 스택 사용

 public static String dfs(int v, boolean node[][]) {
     StringBuilder sb = new StringBuilder();
     Stack<Integer> stack = new Stack<>();
     boolean visited[] = new boolean[n+1];
     stack.add(v);
     int idx;
     while(!stack.isEmpty()) {
         idx = stack.pop();
         if(visited[idx])
             continue;
         visited[idx] = true;
         sb.append(idx+" ");
         for(int i=0; i<n; i++)
             if(node[idx][i] && !visited[i])
                 stack.add(i);
     }
     return sb.toString();
 }

 

DFS를 언제 사용할까?

• 모든 노드를 방문하고자할 때 사용
• 깊이로 들어감에 있어서 조건을 만족시켜야하는 경우에 유용
• 경로의 특징을 저장해둬야 하는 문제 :ex) 각 정점에 숫자가 적혀있고 a부터 b까지 가는 경로를 구하는데, 경로에 같은 숫자가 있으면 안 된다는 문제 등, 각각의 경로마다 특징을 저장해둬야 할 때는 DFS를 사용한다. (BFS는 경로의 특징을 가지지 못한다)

 

시간복잡도

• DFS의 시간복잡도는 그래프를 어떤 방법으로 구현했는지에 따라 달라진다.
  1. 인접행렬에서의 시간 복잡도 (* N = 정점의 수, E = 간선(노드)의 수)
     • 모든 정점을 다 찾아봐야 하기 때문에 dfs(x)의 시간 복잡도 : O(V)
     • dfs(x)가 N번 호출 ⇒ 전체 dfs 알고리즘의 시간복잡도 : O(N*N) = O(N^2)
  2. 인접리스트에서의 시간 복잡도 (* N = 정점의 수, E = 간선(노드)의 수)
     • 인접행렬과 마찬가지로 dfs(x)는 N번 호출
     • dfs(x)의 시간복잡도 : O(N+E)
       • 인접리스트에서 dfs가 호출되는 방법은 모든 정점을 다 찾는 인접행렬의 탐색 방법과 다르다.

 

Reference

https://devuna.tistory.com/32

https://kwin0825.tistory.com/111