깊이 우선 탐색(DFS), 너비 우선 탐색(BFS)

깊이 우선 탐색 (DFS : Depth First Search) 대표적으로 백트래킹에 사용한다. 일반적으로 재귀 호출을 사용하여 구현하지만, 단순한 스택 배열로 구현하기도 한다. 구조상 스택 오버플로우를 유의해야 한다. 자동 미로 생성에 많이 사용 되는 알고리즘! 장점 현 경로상의 노드만 기억하면 돼서 저장공간의 수요가 비교적 적다. 목표 노드가 깊은 단계에 있을 경우 해를 빨리 구할 수 있다. 단점 해가 없는 경로에 깊이 빠질 수 있다. ( 임의 깊이까지만 탐색하도록 만들기! ) 얻어진 해가 최단 경로가 아닐 수도 있다. 왜냐? DFS는 일단 해를 찾으면 탐색이 끝나기 때문이다. 동작 방식 트리나 그래프에서 한 루트로 탐색하다가 특정 상황에서 최대한 깊숙이 들어가서 확인한 뒤 다시 돌아가 다른 루트로 ..

원문링크 : 깊이 우선 탐색(DFS), 너비 우선 탐색(BFS)