[알고리즘 / C++] DFS(깊이 우선 탐색) 알고리즘 개념 및 스택과 재귀를 활용한 구현
DFS(Depth First Search) 알고리즘 DFS(깊이 우선 탐색) 역시 앞서 포스팅했던 BFS 알고리즘과 마찬가지로 길찾기 알고리즘을 구현할 때 유용한 그래프 탐색 알고리즘입니다. Brute Force(완전탐색) 형태로 모든 경우의 수를 다 시도하여 답을 찾는 방법으로, 이름과 같이 깊이(Depth)를 끊임없이 추적하며 전체 정점을 탐색합니다. 앞서 인접행렬과 BFS탐색 알고리즘에서 보였던 아래와 같은 그래프와 인접행렬을 예로 들어보겠습니다. 1부터 탐색을 시작한다고 가정할 때, BFS가 2와 3을 큐에 담는 것과 달리, DFS는 오직 가장 근접한 값인 2만 스택에 담습니다. 그리고 두번째 뎁스인 2에서 다음 탐색을 이어갈 정점을 찾습니다. 1,4,5가 2와 연결되어있지만, 1은 이미 탐색을 ..