[알고리즘] 깊이 우선 탐색(DFS), 너비 우선 탐색(BFS)

DFS (깊이 우선 탐색, Depth First Search) DFS는 그래프에서 깊은 부분을 우선적으로 탐색합니다. 한 정점에서 시작해 다음 경로로 넘어가기 전에 해당 경로를 완벽하게 탐색할 때 사용합니다.

특징 스택 자료 구조에 기초하며, 구현할 때 재귀 함수로 구현하는 것이 좀더 간편합니다. DFS를 구현할 때, 그래프 탐색의 경우 어떤 노드를 방문했었는지 여부를 검사하지 않을 시 무한 루프에 빠질 위험이 있으므로 반드시 검사해야합니다. ( visited[index] = true; ) 미로를 탐색할 때, 해당 분기에서 갈 수 있을 때까지 계속 가다가 더 이상 갈 수 없게 되면 다시 가장 가까운 갈림길로(새로운 분기)로 돌아와서 다른 방향으로 다시 탐색을 진행하는 방법과 유사합니다.

모든 경우를 하나.....