[Algorithm] 깊이우선탐색(DFS)

1. 깊이우선탐색(DFS)란,

Depth First Search

그래프 전체를 탐색하는 방법 중 하나로,

시작점에서 시작하여 다음 분기(branch)로 넘어가기 전 해당 분기를 완벽하게 탐색하고 넘어가는 방법이다.

2. DFS 구현

스택이나 재귀함수로 구현한다.

1. 탐색 시작 노드를 스택에 삽입하고 방문한 것으로 처리한다.
2. 스택 최상단 노드에 방문하지 않은 인접한 노드가 하나라도 있다면 그 노드를 스택에 넣고 방문한 것으로 처리한다.
   방문하지 않은 인접 노드가 없으면 스택에서 최상단 노드를 꺼낸다.
3. 2번 과정을 수행할 수 없을 때까지 반복한다.
   

//A는 0, B는 1, C는 2, D는 3, E는 4라고 본다.

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

int visited[5];
vector<int> adj[5]; // adj[i]. i에 인접한 노드들 저장 

void DFS(int pos)
{
    visited[pos] = 1;
    cout << pos << " ";
    for(int i = 0; i < adj[pos].size(); ++i) // 인접한 노드만큼 탐색
    {
    	int tmp = adj[pos][i];
        if(!visited[tmp]) DFS(tmp); // 재귀적으로 방문
    }
}

int main()
{
    /* 예시에서 사용한 그래프 정의 */
    adj[0].push_back(1);
    adj[0].push_back(2);
	
    adj[1].push_back(0);
    adj[1].push_back(3);
    
    adj[2].push_back(0);
    adj[2].push_back(3);
    adj[2].push_back(4);
    
    adj[3].push_back(0);
    adj[3].push_back(1);
    adj[3].push_back(2);
    adj[3].push_back(4);
    
    adj[4].push_back(2);
    adj[4].push_back(3);
    
    /* 주어진 adj 배열이 정렬되어 있지 않은 경우 정렬을 통해 정점 번호가 작은 것부터 방문하도록 함*/
    for(int i = 0; i < 5; ++i) // 여기서 5는 노드의 개수
    	sort(adj[i].begin(), adj[i].end());
    
    DFS(0); // 여기서 0은 탐색을 시작할 노드
    
    return 0;
}

3. 장단점

1) 장점

• 현 경로상의 노드만 기억하면 되므로 저장공간의 수요가 비교적 적다.
• 목표노드가 깊은 단계에 있을 경우 해를 빨리 구할 수 있다.

2) 단점

• 해가 없는 경로에 깊이 빠질 수 있다.
• 얻어진 해가 최단 경로가 된다는 보장이 없다.

<참고>
블로그1 https://silver-g-0114.tistory.com/35
블로그2 https://better-tomorrow.tistory.com/entry/DFS-BFS-%EC%9D%B4%ED%95%B4%ED%95%98%EA%B8%B0