DFS/BFS (깊이 우선 탐색/너비 우선 탐색)

 이 문제를 다 풀고 나서 다른 사람들이 짜놓은 코드를 보는데 'DFS'라는 개념이 등장했다. 이전부터 어렴풋이는 알고 있었지만 막상 코드를 읽으니 어떻게 돌아가는지 머릿속에 잘 그려지지 않았다. 어차피 공부해야 하는 내용이니 이참에 확실히 짚고 넘어가야겠다 싶어 정리해보았다.

---

先요약

	DFS	BFS
동작 원리	스택	큐
구현 방법	재귀 함수	큐 활용

---

🤔 DFS(Depth First Search, 깊이 우선 탐색)

🗣 그래프에서 깊은 부분부터 탐색하는 알고리즘. 스택 자료구조 활용.

 

동작 과정

1. 탐색 시작 노드를 스택에 삽입하고 방문 처리
2. 스택의 최상단 노드에 방문하지 않은 인접 노드가 있으면 그 인접 노드를 스택에 넣고 방문 처리. 방문하지 않은 인접 노드가 없으면 스택에서 최상단 노드 pop
3. 위의 과정 반복

노드 탐색 순서
1 → 2 → 7 → 6 → 8 → 3 → 4 → 5

---

🤔 BFS(Breadth First Search, 너비 우선 탐색)

🗣 가까운 노드부터 탐색. 큐 자료구조 활용.

 

동작 과정

1. 탐색 시작 노드를 큐에 삽입하고 방문 처리.
2. 큐에서 노드를 꺼내 해당 노드의 인접 노드 중에서 방문하지 않은 노드를 모두 큐에 삽입하고 방문 처리.
3. 위의 과정을 반복.

노드 탐색 순서
1 → 2 → 3 → 8 → 7 → 4 → 5 → 6