동빈북 5장 내용 정리 DFS/BFS

DFS/BFS는 결국 그래프를 탐색하는 방법이다.

그래프는 아래 그림처럼 노드와 간선으로 이루어 진다.

DFS/BFS는 간선으로 연결된 노드를 탐색하는 방법이다. 즉, 인접해 있는 노드를 탐색하는 알고리즘이다.

나타내는 방법은 인접 행렬 방식과 인접리스트 방식이다. 하지만 방문 순서가 다르다.

DFS는 트리에 연결된 노드를 쭉 따라서 깊이에 따라서 탐색하는 방식이고 BFS는 이름 그대로 대상 노드에 연결된 모든 노드를 우선 탐색하는 방식이다.

DFS는 Stack으로 BFS는 큐로 구현한다.

DFS의 경우 재귀함수가 Stack으로 동작하기 때문에 재귀함수를 이용하여 직관적으로 구현할 수 있다.

DFS를 응용한 백트래킹이라는 알고리즘도 존재한다.

트리로 동작이 되었다면 트리의 깊이를 따라서 탐색하다가 그 가지가 의미가 없으면 가지치기 한다.

트리의 끝까지 들어갔는데 원하는 답이 나오지 않으면 들어갔던 경로를 다시 이전 노드로 돌아갔다가 다시 탐색을 진행한다.