[알고리즘] DFS

👌 깊이 우선 탐색 DFS (Depth-first Search)

루트 노드에서 시작해서 다음 분기 (branch)로 넘어가기 전에 해당 분기를 완벽하게 탐색, 넓게 탐색하기 전에 깊게 탐색, 모든 노드를 방문하고자 하는 경우, 검색 속도 자체는 BFS에 비해 저조

✔ 알고리즘

1. 시작 노드 방문
2. 해당 노드에 연결된 노드 중 방문하지 않은 노드를 방문
3. 연결된 노드에 대한 재귀적 호출

✔ 특징

자기 자신을 호출하는 순환 알고리즘 (Recursive)

✔ 시간복잡도

정점의 수가 N, 간선의 수가 E일때:
-인접 리스트로 표현된 그래프: O(N+E)
-인접 행렬로 표현된 그래프: O(N^2)

👉 관련 문제

• 백준 2667 - 단지번호붙이기

👍 참고 사이트

• [알고리즘] 깊이 우선 탐색(DFS)이란