본문으로 건너뛰기
실습하기

깊이 우선 탐색(DFS)이란?

깊이 우선 탐색은 그래프 또는 트리를 탐색할 때, 한 노드에서 시작하여 각 분기를 가능한 한 깊게 탐색하는 알고리즘입니다.


키워드​

  • 스택(Stack): DFS는 스택을 사용하여 이미 방문한 노드를 추적합니다.

  • 재귀(Recursion): 스택을 명시적으로 사용하지 않고, 재귀 호출을 통해 구현될 수 있습니다.

  • 경로 탐색: DFS는 시작 노드에서 목표 노드까지의 경로를 찾는데 자주 사용됩니다.

  • 시간 복잡도: (O(|V| + |E|)), 여기서 (|V|)는 정점의 수, (|E|)는 간선의 수입니다.


DFS의 단계별 과정​

  1. 노드 선택: 탐색을 시작할 노드를 선택합니다.

  2. 방문 및 탐색: 선택한 노드를 방문하고, 인접한 노드 중 방문하지 않은 노드로 이동합니다.

  3. 재귀적 탐색: 각 노드에서 재귀적으로 DFS를 수행하여, 가능한 깊게 탐색합니다.

  4. 탐색 완료: 더 이상 방문할 노드가 없을 때 탐색을 종료합니다.


DFS의 특징​

  • 깊이 우선: 각 분기를 끝까지 탐색한 후에 다른 분기로 넘어갑니다.

  • 백트래킹(Backtracking): 이미 방문한 노드나 경로를 되돌아가면서 다른 경로를 탐색합니다.

  • 비순환 그래프(Non-Cyclic Graphs): DFS는 비순환 그래프에서 모든 노드를 방문하는 데 효과적입니다.

  • 탐색 순서: 노드의 탐색 순서는 그래프의 구조와 시작 노드에 따라 달라집니다.


DFS의 장단점​

  • 장점: 간단하고, 모든 노드를 방문하는 것을 보장합니다. 메모리 사용이 상대적으로 적습니다.

  • 단점: 최단 경로를 찾는데는 적합하지 않을 수 있습니다. 순환 경로가 있는 그래프에서는 무한 루프에 빠질 위험이 있습니다.

다음 내용이 궁금하다면?

코드프렌즈 PLUS 멤버십 가입 or 강의를 등록해 주세요!