[Algorithm] BFS & DFS

- BFS

탐색을 할 때 너비를 우선으로 하여 탐색을 수행하는 탐색 알고리즘.

너비 우선 탐색은 '최단 경로'를 찾아준다는 점에서 최단 길이를 보장해야 할 때 사용된다. 대표적인 예로 미로찾기를 할 때 많이 쓰인다.

알고리즘 

- 큐에서 하나의 노드를 꺼낸다

- 해당 노드에 연결된 노드 중 방문하지 않은 노드를 방문하고, 차례대로 큐에 삽입한다.

Queue를 사용해 구현 가능하다.

1. 맨 위의 start 노드를 큐에 삽입

2. 삽입한 노드는 '방문 처리'를 해준다

3. 이후 알고리즘에 따라 진행

- DFS 

맹목적으로 각 노드를 탐색 할 때 사용된다. 깊이 우선 탐색. 

Stack이 사용된다. 기본적으로 컴퓨터는 stact frame을 사용하기 때문에 단순한 재귀함수만 사용해도 구현할 수는 있다.

BFS와 진행 과정은 비슷하나 Stack을 사용한다는 것만 다르다.