소프트웨어개발블로그 소프트웨어개발블로그

개요 깊이우선탐색은 대표적인 그래프 탐색 알고리즘이다. 위와 같은 그래프를 탐색하고자 한다. 간선으로 연결된 노드를 더 이상 간선이 연결되지 않을 때 까지 탐색하는 방법을 깊이 우선 탐색이라 한다. 간선으로 연결된 모든 노드를 우선으로 탐색하고, 더 이상 해당 노드에 연결된 간선이 없을 경우 하위 노드에서 같은 방식으로 연결된 모든 노드를 탐색하는 것을 너비 우선 탐색이라고 한다. 너비 우선 탐색은 다음 글에서 살펴보기로 하고, 이번 글에서는 DFS 에 대해 자세히 알아보자. DFS (Depth First Search) 1.1 설명 1번 노드에서 시작한다. 연결된 간선이 있으니, 2번 노드부터 탐색한다. 2번 노드로 이동했다. 간선으로 연결된 3번 노드로 이동한다. 3번 노드로 이동했다. 간선으로 연결된..