TIL 웹개발 - DFS, BFS
DFS(Depth Fisrt Search) 깊이우선탐색으로 말 그대로 연결된 노드 트리를 따라 끝까지 탐색 후 다시 올라와 나머지를 탐색한다. 위와 같은 노드 트리를 탐색한다면 순서는 아마 [0, 1, 3, 4, 2]가 될 것이다. DFS를 재귀함수로 구현한 코드다. 함수에 함수가 쓰여 조건이 달성될 때까지 반복한다. BFS( Breadth First Search) 너비우선탐색으로 노드트리를 위에서 아래로 차례대로 탐색하는 특징을 갖고 있다. DFS와 달리 BFS로 위 노드 트리를 탐색하면 [0, 1, 2, 3, 4]의 순서를 가진다. 코드로 표현하면 아래와 같다. deque를 사용해 탐색할 노드의 맨 앞에서부터 가져오기때문에 아래에서 위로 순차적인 탐색이 가능하다. dfs, bfs의 특징을 이용해 풀 수 있는 문제가 나뉘기도하고 혹은 두 방법으로 동일한 문제를 풀 수도 있다.
- 서경태