깊이 우선 탐색(DFS)

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

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

• 넓게(wide) 탐색하기 전에 깊게(deep) 탐색하는 것이다.
• 모든 노드를 방문하고자 하는 경우에 이 방법을 선택한다.
• 깊이 우선 탐색(DFS)는 너비 우선 탐색(BFS)보다 간단하다.
• 단순 검색 속도 자체는 너비 우선 탐색(BFS)에 비해서 느리다.

✔️ 깊이 우선 탐색(DFS) 특징

• 자기 자신을 호출하는 순환 알고리즘 형태를 가지고 있다.
• 전위 순회(Pre-Order Traversals)를 포함한 다른 형태의 트리 순회는 모두 DFS의 한 종류이다.
• 그래프 탐색의 경우, 어떤 노드를 방문했는지 여부를 반드시 검사해야한다.
  (방문 여부를 검사하지 않을 경우 무한 루프에 빠질 위험이 있다.)
  

✔️ 깊이 우선 탐색(DFS) 과정

1. A노드(시작 노드) 방문한다.
   → A노드는 방문했음을 표시한다.

2-1. A와 인접한 노드들을 차례로 순회한다.
→ A와 인접한 노드가 없다면 종료한다.

2-2. A와 인접한 노드인 B를 방문했다면, A와 인접한 또 다른 노드를 방문하기 전에 B와 인접한 노드들을 전부 방문해야한다.
→ B를 시작 정점으로 DFS를 다시 시작하여 B와 인접한 노드들을 방문한다.

1. B의 분기를 완벽하게 탐색하고, A와 인접한 다른 노드 중에서 방문하지 않은 노드를 찾는다.
   → 모든 노드를 방문했다면, 종료한다.
   → 모든 노드를 방문하지 않았다면, 그 노드를 시작 노드로 다시 DFS를 시작한다.

✔️ 깊이 우선 탐색(DFS) 시간 복잡도 및 구현

• 인접 행렬로 구현: O(n^2)

vector<vector<int>> adjacent;
vector<int> visited;

void dfs(int node)
{
    visited[node] = true;
    
    for(int i = 0; i <= adjacent.size(); i++)
    {
    	if(adjacent[node][i] == 1 && !visited[i])
    		dfs(i);
    }
}
// N개의 정점을 모두 방문하는 N번의 loop

• 인접 리스트로 구현: O(n+e)

vector<vector<int>> adjacent;
vector<int> visited;

void dfs(int node) 
{
 
    visited[node] = true;
    
    for(int i = 0; i < adjacent[node].size(); i++)
    {
    	int next = adjacent[node][i];
        if(!visited[next])
        	dfs(next);
    }
}
// DFS 하나당 각 정점에 연결되어 있는 간선의 개수만큼 탐색을 하게 된다.
// 모든 정점을 한 번씩 다 방문하고 모든 간선을 한 번씩 검사

References:
https://gmlwjd9405.github.io/2018/08/14/algorithm-dfs.html
https://currygamedev.tistory.com/10