chapter5. DFS/BFS

탐색(Search)란? -> '많은 양의 데이터 중에서 원하는 데이터를 찾는 과정'

 

       -대표적인 탐색은 DFS, BFS

 

자료구조(Data Struct)란? -> '데이터를 표현하고 관리하고 처리하기 위한 구조'

 

       -대표적인 자료구조 스택과 큐

 

<스택> - First in Last out & Last in First out

              파이썬에서 스택을 이용할 때에는 별도의 라이브러리를 사용할 필요가 없다!

              기본 리스트에서 append() 와 pop()메서드를 이용하면 스택 자료구조와 동일하게 동작한다.

              append()메서드는 리스트의 가장 뒤쪽에 데이터를 삽입하고, pop() 메서드는 리스트의 가장 뒤쪽에서 데이터를 꺼내기 때문이다.

 

<큐> - First in First out

           파이썬에서 큐를 이용할때에는 collections 모듈에서 제공하는 deque 자료구조를 활용하면 된다. deque는 double end queue로 

           스택과 큐의 장점을 모두 채택한 것이다.

 

재귀함수(Recursive Fuction) -> '자기 자신을 다시 호출하는 함수'

 

 

 

DFS

: Depth first Search, 깊이 우선 탐색이라도고 부르며, 그래프에서 기은 부분을 우선적으로 탐색하는 알고리즘 이다.

그래프는 인접행렬과 인접 리스트가 있는데 파이썬에서는 둘다 list로 표현 가능한점을 기억하자.

 

<작동방식>

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

2. 스택의 최상단 노드에 방문하지 않은 인접 노드가 있으면 그 인접 노드를 스택에 넣고 방문 처리를 한다. 방문하지 않은 인접 노드가 없으면 스택에서 최상단 노드를 꺼낸다.

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

 

DFS는 원리상으론 스택을 이용하지만 실제 구현상에는 그냥 재쉬함수를 이용하면 된다.

 

BFS

: Breath Frist Search, 너비 우선 탐색이라는 의미를 가진다. 쉽게 말해 가까운 노드부터 탐색하는 알고리즘

선입선출 방식인 큐 자료구조를 이용하면 된다는점 기억.

 

<작동방식>

1. 탐색 시작 노드를 큐에 삽입하고 방문 처리를 한다

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

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