BFS

너비우선 탐색이란 뜻

• 노드의 길이가 가까운 것부터 골고루 탐색한다

• 먼저 도달 가능한 애들부터 탐색한다는 뜻이다

• 큐(Queue)자료구조 사용한다

• 최단 거리 탐색에 유리하다

작동박식

1. 시작 노드를 큐에 넣고 방문 표시

2. 큐에서 노드를 꺼내며 인접한 노드를 차례로 큐에 추가

3. 방문한 노드를 체크하며 중복 탐색 방지

4. 큐가 빌 때까지 반복

DFS

깊이우선 탐색이란 뜻

• 한 방향 끝까지 파고 든다

• 더 이상 갈 수 없으면 뒤로 돌아가(backtracking) 다른 경로 탐색한다

• 보통 재귀함수나 스택을 이용한다

• 경로 탐색에 유리하다

작동방식

1. 시작 노드를 방문

2. 연결된 노드 중 아직 방문하지 않은 노드로 계속 이동

3. 더 이상 이동할 곳이 없으면 이전 노드로 돌아감 (백트래킹)

4. 모든 노드를 방문할 때까지 반복

비교표

시간 탐색도가 같은 이유는 방법이 어떻게 됐든

돌아야할 노드 수는 같기 때문이다

그치만 실제로는 케이스에 따라 속도가 다르니 유의해야한다

그리고…

…

둘중에 뭘 하든 인접 리스트 쓰는게 더 좋다 (소근소근)