[#3] DFS/BFS

스택 (후입선출)

append() // pop()

---

큐 (선입선출)

파이썬을 큐 규현 시 collections 모듈에서 제공하는 deque 자료구조 활용

queue 라이브러리보다 효율적이다.

 

---

재귀함수

: 자기 자신을 다시 호출하는 함수.

파이썬에서는 무한대로 재귀 호출 진행 불가

재귀함수는 수학 시간에 한 번씩 언급되는 프랙털 구조와 비슷하다.

 

재귀함수에서는 종료 조건을 꼭 명시해야 한다.

스택 구조를 활용해야하는 경우 재귀함수를 이용해서 간편하게 대부분 구현이 가능하다.

팩토리얼이 재귀 함수의 대표적인 예시문제

n이 0이거나 1일 때 값은 1

2부터는 n*factorial(n-1)

 

---

탐색 알고리즘 DFS/BFS

DFS : 깊이 우선 탐색(Depth-first search), 그래프에서 깊은 부분을 우선적으로 탐색

후입선출방식 스택 자료구조를 사용

메모리 효율 측면 : 인접행렬 < 인접 리스트

속도 측면 : 인접 행렬 > 인접 리스트

인접 행렬

>> 특정 경로를 탐색하다가 최대한 깊숙이 들어가서 노드 방문 후 다시 돌아가 다른 경로를 탐색한다.

 

<DFS의 스택 자료구조 동작과정>

1. 탐색 시작 노드를 스택에 삽입 후 방문 처리를 한다.

2. 스택의 최상단 노드에 방문하지 않은 인접 노드가 있다면, 인접 노드를 스택에 넣고 방문 처리를 함.

방문하지 않은 인접 노드가 없으면 스택에서 최상단 노드를 꺼냄.

3. 2번 과정을 더 이상 수행할 수 없을 때까지 반복한다.

 

DFS는 O(N)의 시간이 소요된다는 특징이 있다.

 

---

BFS (Breadth First Search) : 너비 우선 탐색

>> 가까운 노드부터 탐색하는 알고리즘이다.

 

선입선출방식 큐 자료구조를 사용

 

<BFS 동작 방식>

1. 탐색 시작 노드를 큐에 삽입 후 방문처리

2. 큐에서 노드를 꺼내 인접 노드 중에 방문하지 않은 노드를 모두 큐에 삽입하고 방문처리를 한다.

3. 2번의 과정을 더 이상 수행할 수 없을 때까지 반복함.

 

실행 수행시간은 BFS >>> DFS

 

---