깊이 우선 탐색 & 너비 우선 탐색 메모

❗️ 공부중인 사람의 글입니다

오늘 데일리 코딩 문제에 깊이 우선 탐색이라는 개념이 등장해서 알아보았다.

https://www.youtube.com/watch?v=_hxFgg7TLZQ

Depth-First Search

한 root의 마지막 child node까지 탐색한 뒤에 다음 branch를 탐색한다.
모든 노드를 방문하고자 하는 경우에 사용

1. 탐색 시작 노드를 Stack에 삽입하고 방문 처리를 한다.
2. 시작 노드(a)의 인접한 노드들(b, c, ...)을 차례로 순회한다.
   인접한 노드가 없으면 종료한다.
3. 인접 노드(b)가 있으면 (b)의 인접 노드를 차례로 순회한다.
4. (b)의 branch를 전부 순회했으면 아직 방문하지 않은 (a)의 인접 노드 (c)를 순회한다.
5. 모든 정점을 탐색하고 종료한다.

Breadth-First Search

root노드에 인접한 노드부터 level 별로 탐색한다.
재귀적으로 동작하지 않는다.
방문하려는 노드에 이전의 방문 여부를 반드시 검사해야 한다.

1. 탐색 시작 노드를 Queue에 삽입하고 방문 처리를 한다.
2. 시작 노드(a)의 인접한 노드(b, c, ...)를 모두 차례로 방문한다.
   이때 (b)와 (c)는 동일한 level이며,
   다음 level인 (b)의 child node를 방문 예정임을 queue에 저장한다.
3. (c)를 순회하고 queue에 저장돼있던 방문 예정인 정점들을 탐색한다.