> For the complete documentation index, see [llms.txt](https://krjaeh0.gitbook.io/j-log/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://krjaeh0.gitbook.io/j-log/programming/cs-fundamentals/algorithms/depthfirstsearch.md).

# DepthFirstSearch

## 1. 알고리즘 개념

완전 이진 트리의 탐색을 위한 알고리즘으로, 리프 노드(leaf node)까지 내려가면서 검색하는 것을 의미한다. 이 알고리즘은 리프에 도달할 때까지 탐색을 진행하고, 더 이상 검색할 곳이 없는 경우에는 이전(부모)노드로 되돌아갑니다. 그리고 가능한 다른 자식 노드로 다시 내려가 탐색을 계속합니다. 이러한 과정은 모든 노드를 방문할 때 까지 반복됩니다.

## 2. 주요 특징

#### 1) 스택(Stack) 또는 재귀 호출(Recursive Calls) 응용

스택을 사용하는 경우, 방문한 노드를 스택에 푸시(push)하고, 더 이상 탐색할 자식 노드가 없으면 스택에서 팝(pop)하여 되돌아갑니다. 재귀 호출을 사용하는 경우, 함수가 자기 자신을 호출하여 노드를 방문하는 방식으로 탐색을 진행합니다.

#### 2) 모든 노드를 방문할 수 있다는 점에서 완전 탐색 방법

특히, 미로 찾기와 같은 문제 해결에 유용하게 사용됩니다.

#### 3) 경로의 특성을 파악하거나, 특정 노드로부터 가능한 모든 경로를 찾아내는 데 적합

예를 들어, 그래프 내의 사이클(cycle)을 탐지하거나, 두 노드 사이의 경로를 찾는 데 사용될 수 있습니다.

## 3. 구현 방식

깊이 우선 탐색의 경우, 트리 노드를 순회하는 순서에 따라 다음과 같이 세 가지 주요 방법으로 더 세분화할 수 있습니다:

{% stepper %}
{% step %}

### 전위 순회(Pre-order Traversal)

노드를 방문한 후, 왼쪽 자식과 오른쪽 자식을 순회합니다. 즉, 루트 → 왼쪽 → 오른쪽 순으로 방문합니다.
{% endstep %}

{% step %}

### 중위 순회(In-order Traversal)

왼쪽 자식을 방문한 후, 노드를 방문하고, 그 다음 오른쪽 자식을 순회합니다. 이 방법은 이진 검색 트리에서 사용될 경우, 노드를 오름차순으로 방문할 수 있습니다. 즉, 왼쪽 → 루트 → 오른쪽 순으로 방문합니다.
{% endstep %}

{% step %}

### 후위 순회(Post-order Traversal)

왼쪽 자식과 오른쪽 자식을 방문한 후, 노드를 방문합니다. 즉, 왼쪽 → 오른쪽 → 루트 순으로 방문합니다.
{% endstep %}
{% endstepper %}

이들 각각의 순회 방법은 트리의 구조와 특정 문제를 해결하는 데 필요한 탐색 순서에 따라 선택됩니다. 예를 들어, 표현식 트리를 평가하거나 복사하는 데 전위 순회나 후위 순회가 사용될 수 있으며, 이진 검색 트리를 오름차순으로 순회하고자 할 때는 중위 순회가 사용됩니다. 이처럼 다양한 순회 방식을 이해하고 적절히 활용하는 것은 트리 기반의 알고리즘을 효과적으로 구현하는 데 매우 중요합니다.

## 4. 마치며

깊이 우선 검색을 사용하는 경우, 탐색의 순서나 선택하는 경로에 따라 탐색의 효율성이 달라질 수 있으며, 탐색 과정에서 방문한 노드의 경로를 기록하는 방법으로 다양한 문제 해결 전략을 구현할 수 있다.


---

# Agent Instructions
This documentation is published with GitBook. GitBook is the documentation platform designed so that both humans and AI agents can read, navigate, and reason over technical content effectively. Learn more at gitbook.com.

## Querying This Documentation
If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question.

Perform an HTTP GET request on the current page URL with the `ask` query parameter, and the optional `goal` query parameter:

```
GET https://krjaeh0.gitbook.io/j-log/programming/cs-fundamentals/algorithms/depthfirstsearch.md?ask=<question>&goal=<endgoal>
```

`ask` is the immediate question: it should be specific, self-contained, and written in natural language.
`goal` is optional and describes the broader end goal you are ultimately trying to accomplish on behalf of the user. GitBook uses it to tailor the answer towards what is most useful for that goal.

The response will contain a direct answer to the question and relevant excerpts and sources from the documentation.

Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.