DFS

1. 문제 제시 : 친구관계

---

2. 그래프 순회(탐색)

• 그래프 순회는 비선형구조인 그래프로 표현된 모든 자료 (정점)를 빠짐없이 탐색하는 것을 의미합니다.
• 두 가지 방법
  • 깊이 우선 탐색(Depth First Search, DFS)
  • 너비 우선 탐색(Breadth First Search, BFS)

---

3. DFS(깊이 우선 탐색)

• 시작 정점의 한 방향으로 갈 수 있는 경로가 있는 곳까지 깊이 탐색해 가다가 더 이상 갈 곳이 없게 되면, 가장 마지막에 만났던 갈림길 간선이 있는 정점으로 되돌아와서 다른 방향의 정점으로 탐색을 계속 반복하여 결국 모든 정점을 방문하는 순회방법입니다.
• 가장 마지막에 만났던 갈림길의 정점으로 되돌아가서 다시 깊이 우선 탐색을 반복해야 하므로 후입선출 구조의 스택을 사용합니다.

---

4. 스택

• 스택(stack)의 특성
  • 물건을 쌓아 올리듯 자료를 쌓아 올린 형태의 자료구조입니다.
  • 선형 구조 :  자료 간의 관계가 1대 1의 관계를 갖습니다.
  • 비선형 구조 : 자료 간의 관계가 1대N의 관계를 갖습니다. (예 : 트리)
• 마지막에 삽입한 자료를 가장 먼저 꺼냅니다.
  • 후입선출(LIFO, Last-In-First-Out) 이라고 부릅니다.

---

5. 스택의 구현

---

6. DFS(Depth First Search)

---

7. 연습 문제