dfs

[자료구조] DFS (Depth-First Search)

깊이 우선 탐색 (DFS, Depth-First Search) DFS는 깊이 우선 탐색이라고 부르며 그래프에서 깊은 부분을 우선적으로 탐색하는 알고리즘이다. 백트래킹에 사용하는 대표적인 탐색 알고리즘. 이진 트리 순회 알고리즘과 상당이 유사하다. BFS와 마찬가지로 어떤 정점을 방문했는지 반드시 기록한다. ⇒ 이렇게 하지 않으면 무한루프에 빠질 위험이 있다. 루트 노드 혹은 임의의 노드에서 시작해서 다음 분기로 넘어가기 전에 해당 분기를 완벽하게 탐색하는 방식이다. 주로, 재귀함수 또는 Stack으로 구현할 수 있다. 미로를 탐색할 때 한 방향으로 갈 수 있을 때까지 계속 가다가 더 이상 갈 수 없게 되면 다시 가장 가까운 갈림길로 돌아와서 이곳으로부터 다른 방향으로 다시 탐색을 진행하는 방법과 유사. ..