[leetCode] D-7~9. Breadth-First Search/Depth-First Search이란?

너비 우선탐색 (BFS)

그래프 전체를 탐색하는 방법 중 하나로, 특정 노드에서 시작해서 인접한 노드를 먼저 탐색하는 방법
가까운 노드부터 먼 노드 순으로 넓게 탐색한다.
주로 두 노드 사이의 최단 경로 혹은 임의의 경로를 찾고 싶을 때 사용한다.
큐라는 자료에 정점을 다 담아놓은 뒤 pop 하는 방식으로 주로 구현한다.

장점

• 노드의 수가 적고 깊이가 얕은 경우 빠르게 동작할 수 있다.
• 단순 검색 속도가 깊이 우선탐색(DFS)보다 빠르다.
• 너비를 우선 탐색하기에 답이 되는 경로가 여러개일때 최단경로를 보장한다.
• 최단 경로가 존재한다면 어느 한 경로가 무한히 깊어진다 해도 최단 경로를 반드시 찾을 수 있다.

단점

• 재귀호출의 DFS와는 달리 큐에 탐색할 정점들을 저장해야해 저장공간을 많이 필요로 한다.
• 노드의 수가 늘어나면 탐색해야 하는 노드 또한 많아져 비현실적이다.

깊이 우선탐색 (DFS)

특정 노드에서 시작해 다음 branch로 넘어가기전 해당 branch를 완벽하게 탐색하는 방법
모든 노드를 방문하고자 하는 경우 이 방법을 선택한다.
BRS보다 간단한 로직을 갖고 있지만 검색속도는 더 느리다.

자기 자신을 호출하는 순환 알고리즘의 형태를 갖고 있다.
따라서 무한 루프를 방지하기 위해 어떤 노드를 방문했었는지 검사하는 로직을 만들어야 한다.

관련문제 풀이 (leetCode)

🔆 D-7

• [leetCode] 733. Flood Fill
• [leetCode] 695. Max Area of Island

🔆 D-8

• [leetCode] 116. Populating Next Right Pointers in Each Node
• [leetCode] 617. Merge Two Binary Trees

자바스크립트 문제풀이

• [Algorythm][JS][DFS] 부분집합 구하기

• [Algorythm][JS][DFS] 합이 같은 부분집합

Reference

• https://coding-factory.tistory.com/612
• [알고리즘] 너비 우선 탐색(Breadth-First Search)과 깊이 우선 탐색(Depth- First Search)
• https://gmlwjd9405.github.io/2018/08/14/algorithm-dfs.html