🟨 DFS (Depth First Search)
갈수 있을 때까지 가본뒤에 더이상 갈데가 없으면 돌아오는 방법으로 트리의 순회방법중 하나인 깊이우선탐색이다.
예를 들어, 미로에 들어섰다면 우선 내앞에 있는길에서 갈수 있는데 까지 가보고,
만약에 길이 없다면 돌아나와서 마지막 갈림길에서 다른길로 가보고,
또 길이 없다면 돌아나와서 마지막 갈림길 바로 전의 갈림길에서 또 다른길로 가보는 그런 과정과도 같다.
따라서, 길을 잘 선택하면 굉장히 빠르게 미로를 탈출할 수도 있지만, 첫 선택이 잘못 되는 순간 미로전체를 다 헤메고, 갈 수 있는 모든 길을 가본 뒤에야 탈출하게 될 수도 있다.
또한 내가 지나온 길이 가장 빠른길이라고는 절대 확신할 수 없다.
트리입장에서 DFS를 살펴보면,
장점은,
- 저장공간의 필요성이 적음. 갈림길에 해당하는 백트랙킹을 해야하는 노드들만 저장해주면 됨.
- 찾아야하는 노드가 깊을 단계에 있을 수록, 그 노드가 왼쪽에 위치할수록 BFS보다 유리하다.
단점은,
- 답이 아닌 경로가 매우 깊다면, 그 경로에서 오랜시간동안 빠져있을 수 있다는 것.
- 찾은 해가 최적의 경로, 최적의 답이라는 보장이 없음.
이라고 할 수 있다.
🟩 BFS
주변에 있는걸 다 돌아본 후에 다음 깊이에 대해서 진행하는 방법으로 트리의 순회방법중 하나인 너비우선탐색이다.
예를 들어, A사람이 B사람과 소개팅을 하고 싶다고 하자.
그러면 A는 A가 알고있는 친구들에게 B와 아는지 물어보고, A의 친구들이 다시 또 그들의 친구들에게 물어보고, 그 사람들이 또 주변에서 찾는 그런 과정이라고 할 수 있다.
만약에, A가 아는 C가 아는 D가 친구로 B를 알고 있고, A가 아는 친구인 C가 아는 친구인 D가 아는 친구인 E도 B를 알고 있다고 하자.
- A-C-D-B
- A-C-D-E-B
물론 A가 B와 아는 사람을 알게 된다고 해서 소개팅이 되는건 아니지만,
결과적으로, A사람과 B사람이 소개팅을 하게된다면, A와 B 사이에 최소한의 인물인 C, D만 거치면 연락할 수 있다는 것을 확신할 수 있다.
그러나, 이 경우 A사람의 주변인 모두가 A가 B를 찾고 있다는 것을 알게되고, A사람의 주변인의 주변인도 물어봐야하므로, 시간이 오래 소요될 수 있다.
또한, 만약 A사람이 파워 E성향이라서 아는 사람이 많다면, 결과적으로 모든 지인들의 지인들의 지인들까지 물어볼 수 없게 되므로 비현실적이라고 할 수 있다.
이걸 이제 트리입장에서 살펴보면,
BFS의 장점은,
- 너비우선탐색이기 때문에, 답이 되는 경로가 여러개인 경우에도 최단경로를 보장함.
- 최단 경로가 존재한다면, 어느 한 경로가 무한히 깊다고 해도 반드시 최단 경로를 찾을 수 있음.
- 노드 수가 적고, 깊이가 얕은 답이 존재할 때 유리한 탐색방법.
반대로 BFS의 단점은,
- 탐색할 노드들을 저장하는 자료구조로 큐를 사용하기 때문에, 노드의 수가 많을 수록 필요없는 노드들까지 저장해야하는 메모리 비용이 많이 요구됨. DFS에 비해 더 큰 저장공간이 필요함.
- 노드의 수가 많아질수록 탐색해야하는 노드가 많아지기 때문에 비현실적, 비효율적.
이라고 할 수 있다.
🟪 그림
