DFS

1. DFS란?

DFS는 "깊이 우선 탐색"이라는 말 그대로,

한 정점에서 시작해서 갈 수 있는 만큼 계속 깊이 들어갔다가, 더 이상 못 가면 다시 돌아와서 다른 경로를 탐색하는 방식이야.

---

2. DFS의 핵심 원리

DFS는 보통 스택(Stack) 구조로 동작해.

• 재귀 함수로 구현하면, 시스템 콜 스택을 자연스럽게 사용하게 되고
• 반복문으로 구현할 땐 명시적으로 스택을 사용하게 돼.

탐색 흐름 요약:

1. 시작 노드를 방문하고
2. 인접한 노드 중에서 아직 방문하지 않은 노드가 있다면 그 노드로 이동
3. 이동한 노드에서 다시 위 과정을 반복
4. 더 이상 방문할 곳이 없으면 이전 노드로 돌아가서 다른 경로 탐색
5. 모든 노드를 방문할 때까지 반복

---

3. 예시로 살펴보자

그래프:

1
| \
2  3
   |
   4

DFS(1)의 탐색 순서 예시:

1 → 2 → 3 → 4

(인접 리스트 순서에 따라 탐색 순서는 바뀔 수 있어)

DFS 재귀 호출 흐름 예시:

• 시작: dfs(1) 호출
• 방문: 1
  • 인접한 2 → dfs(2) 호출
    • 방문: 2 → 인접 노드 없음 → 복귀
  • 복귀: dfs(1) → 다음 인접한 3 → dfs(3) 호출
    • 방문: 3 → 인접한 4 → dfs(4) 호출
      • 방문: 4 → 인접 노드 없음 → 복귀
    • 복귀: dfs(3) → 종료
  • 복귀: dfs(1) → 종료

---

4. DFS에 필요한 구성 요소

• 그래프: 인접 리스트 형식이 일반적
• 방문 여부 리스트: 중복 방문 방지
• 스택 or 재귀 호출: 깊이 탐색 구현

---

5. DFS의 특징

항목	설명
탐색 순서	깊이 있는 노드부터 탐색
사용 자료구조	스택 (혹은 재귀 호출을 통한 시스템 콜 스택)
재귀?	(보통 재귀로 구현함)
경로 찾기 문제	백트래킹, 순열 조합, 미로 탐색 등에서 유용
시간 복잡도	O(V + E) (V: 정점 수, E: 간선 수)

---

6. BFS와의 차이점

기준	DFS	BFS
탐색 순서	깊이 우선	너비 우선
자료구조	스택 (또는 재귀)	큐 (Queue)
구현 방식	보통 재귀 기반	반복문 기반
사용 예시	백트래킹, 퍼즐, 조합 탐색 등	최단 거리, 네트워크 탐색 등

---

DFS가 자주 쓰이는 문제 유형

• 미로 찾기 문제
• 연결 요소의 개수 구하기
• 섬의 개수 찾기
• N-Queen 문제
• 순열/조합 생성
• 특정 조건을 만족하는 경로 탐색

---

DFS vs BFS 시각적 비교

예제 그래프:

    1
   / \
  2   3
     / \
    4   5

DFS 탐색 순서 (1에서 시작):

1 → 2 → 3 → 4 → 5

• 스택/재귀 흐름:
  • dfs(1)
    • dfs(2) → 복귀
    • dfs(3)
      • dfs(4) → 복귀
      • dfs(5) → 복귀

BFS 탐색 순서 (1에서 시작):

1 → 2 → 3 → 4 → 5

• 큐 흐름:
  • 1 (큐: [1])
  • 2, 3 추가 (큐: [2, 3])
  • 4, 5 추가 (큐: [3, 4, 5])
  • 순차적으로 큐에서 꺼내며 방문

요약 비교표:

구분	DFS	BFS
자료구조	스택 or 재귀 호출	큐 (Queue)
방문 순서	한 방향으로 계속 깊이 들어감	가까운 정점부터 차례로 탐색
사용 목적	모든 경로 탐색, 백트래킹 등	최단 거리 탐색, 네트워크 탐색 등
구현 방식	재귀 함수 or 명시적 스택	반복문 + 큐 활용

---

컴퓨터적 사고 흐름

• "일단 한 방향으로 갈 수 있을 만큼 끝까지 가보자"
• "더 이상 갈 수 없으면, 그제야 돌아와서 다른 경로를 다시 탐색하자"

이게 바로 DFS의 기본 흐름이야~
BFS처럼 넓게 퍼져나가는 게 아니라, 한 줄기 길을 따라 깊게 들어가는 방식이지.

---