DFS : Depth-First Search (깊이 우선 탐색) 이란?

[출처 : https://en.wikipedia.org/wiki/Depth-first_search]

• 그래프 전체를 탐색하는 하나의 방법으로써, 하나의 가지(branch)를 모두 탐색한 이후에 다음 branch로 이동한다.
• 넓게 탐색하는 것이 아닌, 깊게 탐색하는 방법이다.
• stack 또는 recursive(재귀 함수)로 구현할 수 있다.

DFS의 특징

• 정점 방문 시, 반드시 방문 여부(is_visited)를 검사하고, 방문 시 is_visited를 true로 표시한다.

  정점 방문 여부를 검사하지 않으면 무한 루프에 빠질 수 있다.

• 시간 복잡도(Time complexity): 인접 리스트로 구현시 O(V + E) // 인접 행렬로 구현 시 O(V^2)

• 재귀 함수로 구현시, 별도의 자료구조가 필요하지 않으므로 메모리를 아낄 수 있다.

  (BFS의 경우 quene를 사용해야 하므로 DFS에 비해 메모리를 더 사용할 수 밖에 없다.)

• 얻은 결과가 최단 경로라는 보장이 없다. (반면 BFS는 얻은 결과가 최단 경로이다.)

DFS의 진행

• DFS를 시작할 노드를 정해서 매개변수로 전달한다.

• 전달 받은 매개변수가 현재 노드이므로, 현재 방문 중인 노드를 방문처리 해준다.

  (is_visited[cur] = true)

• 현재 노드와 인접한 노드들을 반복문을 통해 하나씩 접근한다. 해당 노드를 다음 노드(next)로 설정한다.

• 다음 노드(next)를 이전에 방문했는지 확인한다.

  만일 방문했다면 다시 방문할 필요가 없으므로 지나간다. ( continue 문 )

  만일 아직 방문하지 않았다면 DFS를 재귀적으로 호출한다. ( DFS(next); )

• 2~4번을 더 이상 방문할 노드가 없을 때 까지 반복한다.