DFS, BFS 알고리즘

대표적인 탐색 알고리즘

💡 DFS

---

• 깊이 우선 탐색

• 그래프에서 깊은 부분을 우선적으로 탐색하는 알고리즘

• 모든 노드를 방문하고자 하는 경우에 사용

• 스택 or 재귀를 이용

미로를 탐색할 때 한 방향으로 갈 수 있을 때까지 계속 가다가 더 이상 갈 수 없게 되면 다시 가장 가까운 갈림길로 돌아와서 이곳으로부터 다른 방향으로 다시 탐색을 진행하는 방법과 유사

구현 방법

1. 탐색 시작 노드를 스택에 넣고 방문 처리
2. 스택의 최상단 노드에 방문하지 않은 인접한 노드가 하나라도 있으면 그 노드를 스택에 넣고 방문. 방문하지 않은 인접 노드가 없으면 스택에서 최상단 노드를 꺼냄
3. 더 이상 2번의 과정을 수행할 수 없을 때까지 반복

💡 BFS

---

• 너비 우선 탐색
• 가까운 노드부터 탐색하는 알고리즘
• 두 노드 사이의 최단 경로 혹은 임의의 경로를 찾고 싶을 때 사용.

지구 상에 존재하는 모든 친구 관계를 그래프로 표현한 후 A와 B사이에 존재하는 경로를 찾는 경우

구현 방법

1. 현재 노드를 큐에 삽입하고 방문 처리
2. 큐애서 노드를 꺼내 해당 노드의 인접 노드 중에서 방문하지 않은 노드를 모두 큐에 삽입하고 방문 처리

collections의 deque라이브러리 사용하는 것이 좋다.
DFS보다 BFS가 빠른편이다.