DFS (깊이 우선 탐색)

그래프에서 가능한 깊이까지 먼저 탐색한 다음, 더이상 진행될 수❌ → 다시 돌아와 다른 경로를 탐색하는 알고리즘. 

 

💡 DFS의 정당성

✅ 시작정점에서 도달 가능한 모든 정점을 정확히 한 번씩 방문한다.

- DFS는 방문한 정점에 대해 방문 표시를 한다.- 어떤 정점 v를 방문할 때, v에 인접한 정점 w 중, 방문❌ 정점에 대해 재귀적으로 탐색하거나 스택에 넣는다.- 한 번 방문한 정점은 다시 방문❌ → 각 정점은 정확히 1번 방문된다.

 

💡 DFS의 깊이 우선 탐색 특성

✅  DFS는 가능한 깊이까지 탐색을 진행한 후, 막히면 되돌아가서 탐색을 이어간다.

✔ 증명 (DFS 흐름은 다음과 같다.)

1. 현재 정점 v에서 인접한 정점 w를 찾는다.

2. 아직 방문❌ 정점 w 발견 → 그 정점으로 바로 이동해 탐색을 계속한다.

3. 더이상 방문 가능한 인접 정점❌ → 되돌아온다.

이는 스택 or 재귀 호출을 통해 구현되어 현재 탐색 경로를 스택에 저장해두고, 막히면 스택에서 마지막으로 방문한 정점으로 되돌아가는 방식이다.

이 과정으로 DFS는 한 경로를 따라 가능한 멀리 내려갔다가, 더이상 내려갈 수 없을 때 가장 최근 갈림길로 돌아와 다른 경로를 탐색한다.

 

🌐 시간복잡도 : O(|V|+|E|)