DFS와 BFS

DFS와 BFS는 그래프 탐색 방법이다.
오늘은 DFS와 BFS가 노드와 경로를 탐색할 때 어떻게 다른지 적어보려고 한다.

DFS (깊이 우선 탐색)

1. 모든 노드를 1회씩 탐색 가능
: 단, used배열을 복구시키지 않음

2. 모든 경로를 탐색 가능
: 단, used배열을 복구시켜야함

BFS (너비 우선 탐색)

1. 모든 노드를 1회씩 탐색 가능
: 가까운 순으로 탐색하기 때문에 최소 거리를 구하기 매우 효율적

2. 모든 경로를 탐색 가능....
: 그러나, 큐에 used배열을 담아서 기록해야하기 때문에 아주 아주 메모리의 낭비가 심하다!