DFS (Depth-First-Search)

DFS

DFS는 그래프 형태의 data가 있고 원하는 data를 검색할 때 어떤 방법으로 data를 찾을 것인가 하는 방법중의 하나다. Depth-First-Search 깊이 우선 탐색으로 그래프가 탐색이 시작되는 지점부터 자식 노드들을 하나하나 진입해서 더이상 진입할 수 없을때까지 끝까지 들어가서 검색하는 방법이다.

                1
              / ㅣ \
            2   4   8
           /   / \   \
          3   5   7   9
             /
            6

이런 그래프가 있다고 할 때 검색의 시작을 1이라고 하고 우리는 6을 찾는다고 할때 검색의 순서는

                1a
              / ㅣ \
            2a  4b   8
           /   / \   \
          3a  5b   7   9
             /
            6b

1을 찾아보고 다음에 자식 노드인 2, 4, 8 중에 왼쪽부터 차례대로 들어가서 검색한다. 2를 찾아보고 자식노드인 3까지 찾아보고 원하는 6이 나오지 않으니 다시 1의자리로 올라간다. 2는 찾아봤으니 1의 다른 자식노드인 4를 찾아본다. 그리고 4의 자식노드인 5를 먼저 보고 6을 확인 했을때 원하는 값을 찾게된다. 여러 자식 노드가 있을때 어떤 노드를 우선 검색할 것인지는 노드가 입력된 순서대로 하는게 헷갈리지 않는다. 노드의 입력 순서가 대체로는 왼쪽부터 이루어지게 되기 때문에 왼쪽으로 우선 검색을 했다.

이렇게 찾을때까지 모든 깊이를 다 들어가서 하나하나 검색을 하는 방법이 깊이 우선 탐색방법이다.

이 깊이 우선 탐색방법은 재귀함수를 호출하여 찾을 때 더 간편해진다.