7. 깊이 우선 탐색(DFS), 너비 우선 탐색(BFS)

p. 145~179(8일차)

강의:  05-1, 05-2

---

1. 깊이 우선 탐색 DFS *코테에서 가장 많이 사용함

- 그래프 완전 탐색 기법 중 하나

- 시작 노드에서 출발하여 분기를 정하고 최대 깊이까지 탐색을 마친 후 다른 분기로 이동

 

 ✔ 핵심 이론

- 재귀함수로 구현 (FILO 먼저 들어온 데이터가 나중에 나간다)

- 스택 자료구조 이용

 

 ✔ 과정

1. DFS를 시작할 노드를 정한 후 사용할 자료구조 초기화하기

  1) 인접 리스트로 그래프 표현하기

  2) 방문 배열 초기화하가

  3) 시작 노드 스택에 삽입하기

  4) 스택에 시작 노드를 1로 삽입할 때 해당 위치의 방문 배열을 체크 (T, F, F, F ...)

 

2. 스택에서 노드를 꺼낸 후 꺼낸 노드의 인접 노드를 다시 스택에 삽입하기

  1) 스택에서 노드를 꺼내면서 탐색 순서에 꺼낸 노드를 기록 (pop)

  2) 인접 리스트이 인접 노드를 스택에 삽입하며 방문 배열을 체크

  3) 방문 배열 (T, T, T, F, F, F)

 

3. 스택 자료구조에 값이 없을 때까지 반복

- 이미 다녀간 노드는 방문 배열을 바탕으로 재 삽입 하지 않는 것이 핵심!

 

---

2. 너비 우선 탐색 BFS

- 그래프 완전 탐색 기법 중 하나

 

 ✔ 핵심 이론

-  FIFO 탐색 (선입선출 방식)

- Queue 자료구조 이용

- 탐색 시작 노드와 가까운 노드를 우선하여 탐색

- 목표 노드에 도착하는 경로가 여러 개일 때 최단 경로를 보장한다

 

 ✔ 과정

1. BFS를 시작할 노드를 정한 후 사용할 자료구조 초기화

  1) 방문한 노드를 체크하기 위한 배열 필요

  2) 원본 그래프 -> 인접 그래프 -> 방문 배열  -> 큐 자료구조에 시작점 더하기

 

2. 큐에서 노드를 꺼낸 후 꺼낸 노드의 인접 노드를 다시 큐에 삽입하기

  1) 큐에서 노드를 꺼내면서 탐색 순서에 꺼낸 노드를 기록

  2) 대상 노드의 인접 노드를 큐에 삽입

  3) 노드를 삽입하며 방문 배열 체크

 

3. 큐 자료구조에 값이 없을 때까지 반복하기

  1) 큐에 노드가 없을 때 까지 앞선 과정을 반복

     * 선입선출 방식으로 DFS와 다름