99클럽 코테 스터디 18일차 TIL DFS

그래프 탐색 기법: DFS

• DFS (Depth First Search)란?
  
  • 시작 노드부터 다음 분기로 넘어가기 전에 해당 분기를 완벽하게 탐색하는 그래프 탐색 방법
  • 한 방향으로 경로를 탐색하다가 더 이상 갈 수 없으면 다른 방향으로 탐색을 진행
  • Stack이나 재귀 함수(Recursive function)로 구현할 수 있음

그래프

• 그래프 탐색 순서
  
  • 0 -> 1 -> 3 -> 4  -> 2  -> 5  -> 6
• 시간 복잡도
  • 인접 행렬에서의 시간 복잡도: O(V²)
  • 인접 리스트에서의 시간 복잡도: O(V+E)
  • V: 정점(노드)의 개수, E: 간선의 개수
•  

728x90

느낀 점

• 어떤 문제에서 DFS를 사용해야 하는지 파악하는 방법을 알아야겠다.

다음에 학습할 것

• BFS에 대하여
• DFS 직접 구현해보기

반응형

---

DFS에 대해 알아보았다.