[다시] 그래프 탐색 알고리즘 BFS/DFS

프로그래밍에 자주 사용되는 대표적인 자료구조에는 "그래프"가 있습니다.

그래프는 정점과 간선으로 이루어져 있는데 간선을 통해서 모든 정점을 방문하는 것을 그래프를 탐색한다고 합니다.

위에서 언급했듯이 그래프 탐색 알고리즘에는 대표적으로 깊이 우선 탐색(DFS), 너비 우선 탐색(BFS)가 있습니다. 각각의 알고리즘에 대해서 자세히 알아보도록 하겠습니다.

위 그림을 보시면 두 알고리즘의 차이에 대해서 직관적으로 이해하실 수 있습니다. 각 알고리즘의 명칭에서도 볼 수 있듯이 깊이(자식)를 우선으로 탐색하느냐 아니면 너비(형제)를 우선으로 탐색하느냐의 차이가 있습니다.

1. 깊이 우선 탐색

깊이 우선 탐색 (Depth First Search)은 트리 혹은 그래프에서 노드의 자식들을 우선으로 탐색하는, 즉 최대한 깊숙히 탐색한 후 다시 돌아가 다른 루트를 탐색하는 방법입니다. 여기서 한 노드에서 제일 마지막 자식까지 탐색을 마치고 돌아오는 과정을 백트리킹(Backtracking)이라고 합니다. 구현에는 주로 스택 자료구조와 재귀를 사용합니다.

2. 너비 우선 탐색

너비 우선 탐색 (Breadth First Search)은 트리 혹은 그래프에서 노드의 인접한 모든 정점들을 우선으로 탐색하는 방법입니다. 출발 노드에서 목표 노드까지의 최단 길이 경로를 보장하는 방법입니다. 구현에는 주로 큐 자료구조를 사용합니다.