# DFS와 재귀 완전 이해하기

코딩 테스트에서 자주 나오는 DFS(Depth-First Search)와 재귀(Recursion)를 이해하기 쉽게 정리해보기
매번 헷갈려해서 한번 문서화해두는 것이 나중에 참고하기도 편할 것 같다....

---

1. DFS란?

정의

DFS는 “갈 수 있을 때까지 끝까지 탐색하는 방식”이다.

다음과 같은 구조를 생각해보자:

내 방 → 거실 → 부엌
        ↓
       화장실

탐색 순서:

1. 내 방 → 거실
2. 거실 → 부엌 (끝까지 이동)
3. 더 갈 곳이 없으면 되돌아감
4. 화장실 탐색

핵심:

끝까지 간다 → 막히면 돌아온다 → 다른 길 탐색

---

2. DFS 기본 구조

function dfs(node) {
    visited[node] = true;

    for (연결된 노드들) {
        if (아직 방문 안했으면) {
            dfs(다음 노드);
        }
    }
}

---

3. 재귀란?

정의

재귀는 함수가 자기 자신을 다시 호출하는 방식이다.

---

4. 재귀 예시

잘못된 경우 (무한 호출)

function f() {
    f();
}

올바른 경우 (종료 조건 존재)

function countDown(n) {
    if (n === 0) return;

    console.log(n);
    countDown(n - 1);
}

실행 흐름:

countDown(3)
→ 3 출력
→ countDown(2)
    → 2 출력
    → countDown(1)
        → 1 출력
        → countDown(0)
            → 종료

---

5. DFS와 재귀의 관계

DFS는 재귀를 사용해 구현하는 경우가 많다.

function dfs(node) {
    visited[node] = true;

    for (let i = 0; i < n; i++) {
        if (연결 && 방문 안함) {
            dfs(i);
        }
    }
}

의미:

• 현재 노드를 방문
• 연결된 노드 중 방문하지 않은 곳으로 이동
• 그 노드에서도 같은 작업 반복

---

6. 동작 과정

그래프:

0 — 1 — 2

실행:

dfs(0)
 → dfs(1)
   → dfs(2)
     → 종료
   → 복귀
 → 복귀

---

7. 단계별 흐름

1. dfs(0)
   0 방문, 1로 이동

2. dfs(1)
   1 방문, 2로 이동

3. dfs(2)
   2 방문, 더 이상 이동 불가 → 종료

복귀:

dfs(2) → dfs(1) → dfs(0)

---

8. 핵심 요소

1. 방문 처리

visited[node] = true;

2. 탐색 조건

if (연결 && !visited)

3. 재귀 호출

dfs(next);

---

9. 정리

• DFS는 깊이 우선 탐색 방식이다.
• 재귀는 DFS를 구현하는 대표적인 방법이다.
• 탐색은 “끝까지 진행 → 막히면 복귀” 구조로 동작한다.

---

한 줄 요약

DFS는 갈 수 있는 곳까지 계속 들어가는 재귀 기반 탐색이다.