[알고리즘] DFS에 대해서 알아봅시다. - I am yumida

하나의 노드로부터 시작해 차례대로 모든 노드들을 한 번씩 방문하는 그래프 탐색에는 크게 깊이 우선 탐색(DFS)과 너비 우선 탐색(BFS)가 있습니다. 

 

오늘은 DFS에 대해서 알아보겠습니다.

DFS는 루트 노드나 임의의 노드에서 시작하여 최대로 진입할 수 있는 깊이까지 탐색하고 다시 돌아와 다른 노드로 같은 방식으로 탐색합니다.

 

이 그림을 통해 DFS의 원리를 알아보겠습니다. 노드 1에서 시작해서 차례대로 노드 7까지 순회합니다. 진행되는 방향을 보면 한 가지의 끝까지 탐색하고, 그 다음 가지를 순차적으로 탐색합니다. 전체적으로 위에서 아래로 깊게 탐색이 진행되는 것을 볼 수 있습니다. 

 

그림을 자세히 설명하자면 1부터 시작해서 막다른 곳에 다다를 때까지 연속으로 진행되는 탐색이 총 3번에 걸쳐 진행됩니다.

1->2->5->6까지 진행하고 그 다음 5로 되돌아갔다가 다음번 탐색은 7->3, 다시 되돌아 나가 마지막으로 시작 지점까지 올라가서 4를 탐색하고 종료합니다. 즉, 최종 결과는 1->2->5->6->7->3->4 입니다.

 

예를 들면, 미로에서 한 루트로 계속 가다가 막다른 길이면 바로 직전 갈림길로 돌아가 길을 찾는 것이라고 할 수 있습니다. DFS는 전체 정점을 맹목적으로 탐색할 때 사용합니다. DFS의 구현은 재귀 구조, 스택을 이용합니다.

 

 

1. DFS를 재귀 구조로 구현하는 방법을 알아보겠습니다.

 

Python CODE

graph_list = {1: set([2, 3, 4]),
              2: set([5]),
              3: set([5]),
              4: set([]),
              5: set([6, 7]),
              6: set([]),
              7: set([3])}

root_node = 1

def recursive_dfs(v,discovered=[]):
  discovered.append(v)
  for w in graph_list[v]:
    if w not in discovered:
      discovered=recursive_dfs(w,discovered)
  return discovered
recursive_dfs(1)

graph_list는 앞의 그래프를 딕셔너리로 나타낸 것입니다.

 

재귀 구조로 구현하는 과정은 아래와 같습니다.(CODE 해석)

 

1) 시작 노드를 방문한 후, 방문 기록(discovered)에 삽입합니다.

2) 시작 노드와 인접한 노드를 w로 지정합니다.

 

3) 재귀함수 recursive_dfs()에 w와 discovered를 삽입합니다.[이 때, w가 여러 개인 경우 가장 작은 w를 넣습니다]

 

    재귀함수에서 일어나는 과정은 아래와 같습니다.

 

    3-1) w 노드를 방문한 후, discovered에 삽입합니다.

    3-2) w 노드와 인접한 노드들 중 discovered에 없고(방문한 적이 없고) 가장 작은 노드를 선택합니다.

    3-3) 이것을 새로운 w노드로 지정합니다.

    3-4) 재귀함수 recursive_dfs()에 w와 discovered를 삽입합니다.

 

4) 모든 노드를 방문할 때 까지 3-1~3-4 과정을 반복합니다.

 

    4-1) 이 때, 중간에 끊기는 경우가 있습니다. 바로 3-2)에서 w노드와 인접한 노드가 없거나 모두 방문한 경우입니다.

   4-2) 이런 경우 직전 w노드로 돌아가서 해당 w노드와 인접하면서 방문한 적이 없는 노드를 새로 방문하고 3-1에서 다시 시작합니다.

           [예를 들면, 앞의 그림에서 1->2->5->6 에서 끊김을 알 수 있습니다. 이때 5 노드로 다시 돌아가서 방문한 적이 없는 7을

           새로 방문하는 것입니다. 이후 7은 w노드가 되고 discovered에 삽입됩니다.]

 

5) 완성한 discovered가 DFS로 구한 경로입니다.

 

 

2. DFS를 Stack으로 구현하는 방법을 알아보겠습니다.

 

Python CODE

graph_list = {1: set([2, 3, 4]),
              2: set([5]),
              3: set([5]),
              4: set([]),
              5: set([6, 7]),
              6: set([]),
              7: set([3])}

root_node = 1

def iterative_dfs(start_v):
  discovered=[]
  stack=[start_v]
  while stack:
    v=stack.pop()
    if v not in discovered:
      discovered.append(v)
      for w in graph_list[v]:
        stack.append(w)
  return discovered
iterative_dfs(1)

 

Stack으로 구현하는 과정은 아래와 같습니다.(CODE 해석)

 

1) 시작 노드를 방문한 후, Stack에 삽입합니다.

 

2) 가장 최근에 Stack에 삽입된 원소를 꺼내서 v로 지정합니다.

 

3) v가 한번도 방문한 적이 없는 노드인 경우 방문기록(discovered)에 삽입합니다.

 

     3-1) v가 방문한 적이 있는 노드인 경우 2 과정으로 돌아가서 계산합니다.

 

4) v와 인접한 노드들을 차례로 Stack에 삽입합니다. 

 

5) 2~4 과정을 Stack이 비어있을 때까지 반복합니다.

 

 

참고

https://velog.io/@sohi_5/algorithmDFS

[자료구조와 알고리즘] DFS (깊이 우선 탐색)

 

http://www.kyobobook.co.kr/product/detailViewKor.laf?mallGb=KOR&ejkGb=KOR&barcode=9791189909178 

파이썬 알고리즘 인터뷰 - 교보문고