DFS, BFS 모두 그래프에 속하는 알고리즘
그래프
: 정점(node)과 그 정점을 연결하는 간선(edge)으로 이루어진 자료구조의 일종
그래프 탐색
: 하나의 정점으로부터 시작하여 차례대로 모든 정점들을 한 번씩 방문하는 것
DFS - 깊이 우선 탐색 (Depth-First Search)
루트 노드(혹은 다른 임의의 노드)에서 시작해서 다음 분기로 넘어가기 전에 해당 분기를 완벽하게 탐색하는 방식
ex) 미로찾기를 할 때 최대한 한 방향으로 갈 수 있을 때까지 쭉 가다가 더 이상 갈 수 없게 되면 다시 가장 가까운 갈림길로 돌아와서 그 갈림길부터 다시 다른 방향으로 탐색을 진행하는 것
BFS - 너비 우선 탐색 (Breadth-First Search)
루트 노드(혹은 다른 임의의 노드)에서 시작해서 인접한 노드를 먼저 탐색하는 방식
시작 정점으로부터 가까운 정점을 먼저 방문하고 멀리 떨어져 있는 정점을 나중에 방문하는 순회 방법
큐를 이용해서 구현
주로 두 노드 사이의 최단 경로를 찾고 싶을 때 이 방법을 선택