BFS : 늘 내가 더 빨리 찾는 건 아니지만, 최단 거리를 DFS로 하는 건 선 넘었지!!

📖 깊이우선탐색(DFS)이란?

💡 depth-first search
탐색 시 한 방향으로 갈 수 있을 때까지 계속 가다가(leaf node까지) 더 이상 갈 수 없게 되면 다시 가장 가까운 갈림길로 돌아와 다른 방향으로 다시 탐색을 진행하는 순회 방법

• 모든 노드를 방문하고자 할 경우 많이 사용
• 하나의 경우에 대하여 하위 경우의 수를 다 조사하고 다음 경우의 수를 조사하면서 해를 찾는 과정

깊이우선탐색(DFS) 진행 순서 → A-B-D-E-C-F

깊이우선탐색과 스택

- 상황 : 트리 내부 특정 값을 DFS, 스택을 활용하여 탐색
- 준비물 : 트리, 스택, 조건문(찾고자하는 값 판별)

1) 가장 먼저 root부터 조건문에 부합하는지 검사 => A 검사
2) 검사한 값이 찾고자하는 값이 아니면, 그것의 child node들을 스택에 push
stack [C, B]
3) 스택의 가장 마지막 값(LIFO) pop하여 조건문에 부합하는지 검사 => B 검사
stack [C]
4) 검사한 값이 찾고자하는 값이 아니면, 그것의 child node들을 스택에 push
stack [C, E, D]
5) 스택의 가장 마지막 값(LIFO) pop하여 조건문에 부합하는지 검사 => D 검사
stack [C, E]
6) D는 child가 없는 leaf 노드이므로 push 과정 없이 스택의 마지막 값 pop하여 검사 => E 검사
7) 찾고자하는 값을 찾았으므로 알고리즘 종료

=> A → B → D → E 순으로 순회
=> 이러한 방법으로 '미로 찾기(탈출할 수 있는 미로인지 판단)' 문제에서 활용 가능

---

📖 너비우선탐색(BFS)이란?

💡 breadth first search
탐색 시 시작 정점(root)로부터 가까운 정점을 먼저 방문하고(level 1부터 방문) 멀리 떨어져 있는 정점을 나중에 방문하는 순회 방법

• 같은 레벨을 쭉 검사하고 다음 레벨로 넘어가 검사
• 하나의 경우에 대하여 다음 단계의 경우의 수를 조사하면서 level별로 순회하며 해를 찾는 과정

너비우선탐색(BFS) 진행 순서 → A-B-C-D-E-F

너비우선탐색과 큐

- 상황 : 트리 내부 특정 값을 BFS, 큐를 활용하여 탐색
- 준비물 : 트리, 큐, 조건문(찾고자하는 값 판별)

1) 가장 먼저 root부터 조건문에 부합하는지 검사 => A 검사
2) 검사한 값이 찾고자하는 값이 아니면, 그것의 child node들을 큐에 add
queue [B, C]
3) 큐의 가장 앞 값(FIFO) poll하여 조건문에 부합하는지 검사 => B 검사
queue [C]
4) 검사한 값이 찾고자하는 값이 아니면, 그것의 child node들을 큐에 add
queue [C, D, E]
5) 큐의 가장 앞 값(FIFO) poll하여 조건문에 부합하는지 검사 => C 검사
queue [D, E]
6) 검사한 값이 찾고자하는 값이 아니면, 그것의 child node들을 큐에 add
queue [D, E, F]
7) 큐의 가장 앞 값(FIFO) poll하여 조건문에 부합하는지 검사 => D 검사
queue [E]
8) D는 child가 없는 leaf 노드이므로 add 과정 없이 큐의 가장 앞 값 poll하여 검사 => E 검사
9) 찾고자하는 값을 찾았으므로 알고리즘 종료

=> A → B → C → D → E → F
=> 이러한 방법으로 '최단경로 찾기' 문제에서 활용 가능