DFS (깊이 우선 탐색)

 

DFS (Depth-First Search 깊이 우선 탐색)는 그래프나 트리에서 노드를 탐색하는 알고리즘 중의 하나이다. 이 방법은 가능한 깊게 노드를 탐색한 뒤, 더 이상 갈 수 없으면 되돌아가서 다른 노드를 탐색하는 방식이다. 보통 재귀함수의 형태나 Stack 자료 구조를 이용하여 문제를 해결한다. 

 

[동작 원리]

1. 시작 노드를 선택한다
2. 선택한 노드의 인접 노드를 순차적으로 깊게 탐색한다. 
3. 더 이상 탐색할 노드가 없으면, 가장 마지막에 방문했던 노드로 돌아가서 다른 노드를 탐색한다. 
4. 이 과정을 반복하면서 모든 노드를 탐색한다. 

단, 한번 방문한 노드는 또 방문해도 적지 않는다. 

 

예를 들어 아래와  같은 그래프가 있다면,  A - B - D - E - C - F - G   순서로 노드를 탐색할 수 있다. 

D까지 갔을 땐 더 이상의 인접한 노드가 없음으로 다시 B로 돌아와 남은 E 를 수행한다. 

 

[DFS 핵심 이론]

 

• 방문 여부 확인용 배열 

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

boolean[] visited = new boolean[n];

 

• 인접 리스트로 그래프 표현 

원본 그래프로 표기 된 것을 리스트 형태로 깔끔하게 바꾸자. 

 <원본그래프>                      <인접리스트>
 
     A                            A: [B, C]  
   /   \                          B: [D, E]
  B     C           ====>         C: [F, G]
 / \   / \                        D: []
D   E F   G                       E: []
                                  F: []
                                  G: []

 

• 스택(재귀함수)에 삽입하기 

시작노드를 정했다면, 그 시작 노드부터 Stack에 넣어주고 만들어 둔 visited 배열의  A 값을 변경해준다. 

스택: [A]
visited: [A: true, B: false, C: false, D: false, E: false, F: false, G: false]

스택: [A, B]
visited: [A: true, B: true, C: false, D: false, E: false, F: false, G: false]

스택: [A, B, D]
visited: [A: true, B: true, C: false, D: true, E: false, F: false, G: false]

 

A부터 시작하여 A - B - D 순서로 탐색을 완료하였다. 이제 D의 자식 노드가 없음으로 D를 pop 처리를 해준다. 

스택: [A, B]
visited: [A: true, B: true, C: false, D: true, E: false, F: false, G: false]

 

하지만, B에는 또 다른 자식 노드가 있으니 E 를 넣어주고 visited 배열의 값을 바꿔준다. 

스택: [A, B, E]
visited: [A: true, B: true, C: false, D: true, E: true, F: false, G: false]

 

E에도 하위 노드가 없고, B 도 더 이상의 자식 노드가 없음으로 pop으로 모두 빼 준다. 

스택: [A]
visited: [A: true, B: true, C: false, D: true, E: true, F: false, G: false]

 

같은 방식으로 C 를 방문해 주면 된다. 

스택: [A, C]
visited: [A: true, B: true, C: true, D: true, E: true, F: false, G: false]

스택: [A, C, F]
visited: [A: true, B: true, C: true, D: true, E: true, F: true, G: false]

스택: [A, C]
visited: [A: true, B: true, C: true, D: true, E: true, F: true, G: false]

스택: [A, C, G]
visited: [A: true, B: true, C: true, D: true, E: true, F: true, G: true]

스택: [A]
visited: [A: true, B: true, C: true, D: true, E: true, F: true, G: true]

A → B → D → E → C → F → G //최종 탐색 순서