DFS 깊이 우선 탐색

가능한 한 깊이를 우선적으로 탐색해 들어가는 방식

한 노드를 방문하면 그 노드의 자식들을 재귀적으로 계속 탐색

예를 들어, 미로찾기를 할 때 최대한 한 방향으로 갈 수 있을 때까지 쭉 가다가 더 이상 갈 수 없게 되면 다시 가장 가까운 갈림길로 돌아와서 그 갈림길부터 다시 다른 방향으로 탐색을 진행하는 것.

특징

• 백트래킹과 잘 어울림
• 경로를 추적하거나 모든 경우의 수를 탐색할 때 유리
• 깊이 제한이 없으면 무한 루프 발생 가능

구현 방법

• 재귀함수 또는 스택 사용

BFS 너비 우선 탐색

개념

• 루트 노드부터 가까운 노드를 먼저 탐색
• 같은 깊이에 있는 노드를 먼저 모두 방문

주로 두 노드 사이의 최단 경로를 찾고 싶을 때, 이 방법을 선택