dfs.md

DFS(깊이 우선 탐색)

루트 노드 혹은 다른 임의의 노드에서 시작해서 다음 분기(branch)로 넘어가기 전에 해당 분기를 완벽하게 탐색하는 방법

• 미로를 탐색할 때 한 방향으로 갈 수 있을 때까지 계속 가다가 더 이상 갈 수 없게 되면 다시 가장 가까운 갈림길로 돌아와서 이곳으로부터 다른 방향으로 다시 탐색을 진행하는 방법과 유사하다
• 모든 노드를 방문하고자 하는 경우 이 방법을 선택한다
• DFS가 BFS보다 좀 더 간단하다
• 단순 검색 속도 자체는 BFS에 비해서 느리다

DFS 특징

• 자기 자신을 호출하는 순환 알고리즘의 형태를 가진다
• 스택 혹은 재귀를 이용하여 구현이 가능하다
• 전위 순회를 포함한 다른 형태의 트리 순회는 모두 DFS의 한 종류이다
• 이 알고리즘을 구현할 때 가장 큰 차이점은, 그래프 탐색의 경우 어떤 노드를 방문했었는지 여부를 반드시 검사해야 한다는 것이다
  • 이를 검사하지 않을 경우 무한루프에 빠질 위험이 있다

시간 복잡도

• DFS는 그래프(정점의 수 : N, 간선의 수 : E)의 모든 간선을 조회한다
  • 인접 리스트로 표현된 그래프 : O(N+E)
    • 인접행렬과 마찬가지로 dfs(x)는 N번 호출된다
  • 인접 행렬로 표현된 그래프 : O(N²)
    • 모든 정점을 다 찾아봐야 하기 때문에 dfs(x)의 시간 복잡도는 O(N)
    • dfs(x)가 N번 호출되어야 하므로 전체 dfs 알고리즘의 시간복잡도는 O(V²)이다
• 즉 그래프 내에 적은 숫자의 간선만을 가지는 희소 그래프의 경우 인접 행렬보다 인접 리스트를 사용하는 것이 유리하다