그래프는 **노드(Node)**와 **간선(Edge)**로 구성된 자료구조입니다. 여러 개의 점이 선으로 연결되어 있는 구조로, 간선에 방향이 있으면 방향 그래프, 방향이 없으면 양방향 그래프라고 합니다.
<aside> 🔗
그래프에 관한 더 자세한 내용은 다음 게시글을 참고해주세요.
</aside>
그래프 탐색(순회)란 그래프 내의 모든 노드를 한 번씩 방문하여 살펴보는 것을 말합니다.
현실 세계의 많은 것들을 그래프 형태로 표현할 수 있습니다. 가장 쉽게 볼 수 있는 예가 ‘지하철 노선도’입니다. 각각의 역들(Node)이 간선으로 이어져있습니다. 우리는 도착지까지 최단 거리, 최소 환승 등에 따라 경로를 찾습니다. 이 때 그래프 탐색을 사용해서 경로를 찾을 수 있습니다.
그래프 탐색 알고리즘으로는 **깊이 우선 탐색(DFS)**과 너비 우선 탐색(BFS), 두 가지 방식이 존재합니다. 두 알고리즘 모두 모든 노드를 방문하므로 시간복잡도는 **O(노드수 + 간선수)**입니다.
일반적인 그래프 탐색 문제에서는 깊이 우선 탐색과 너비 우선 탐색 모두 사용 가능합니다. 만약 문제가 시작 노드로부터 가까운 노드 순으로 방문해야 하는 경우에는 너비 우선 탐색으로 구현해야합니다.
그래프 탐색은 차후 다익스트라 알고리즘, 크루스칼/프림 알고리즘, 위상 정렬과 같은 다른 알고리즘의 기반이 됩니다.
DFS는 한 방향으로 갈 수 있을 때까지 깊게 내려갔다가, 더 이상 갈 곳이 없으면 돌아와서 다른 방향을 탐색하는 방식의 그래프 탐색 알고리즘입니다. 즉 현재 탐색 중인 노드를 기준으로 해당 노드에 연결된 노드들을 타고 최대한 쭉 내려가서, 깊이를 우선으로 탐색하여 깊이 우선 탐색이라고 부릅니다.
DFS는 예를 들면 미로 길찾기와 같습니다. 갈 수 있는 곳을 따라 계속 앞으로 전진하다가 벽을 만나면 다시 되돌아와서 다른 갈래의 길로 다시 전진하는 것과 같습니다. 그러한 과정을 반복하며 모든 길을 찾는 것입니다.
아래 예시를 통해 자세하게 알아보겠습니다.
만약 예시와 다르게 연결되지 않은 그래프라면 모든 정점에 대해 DFS를 한 번씩 호출해서 모든 노드를 탐색해야합니다.
정리하자면, DFS는 다음 원리에 따라 구현합니다.