그래프 탐색 알고리즘 : DFS/BFS

@ 자료구조 : 스택, 큐

- 파이썬에서는 1)스택 : 기본 자료구조에서 append(), pop() 함수를 이용해 스택 자료구조 사용가능.

                     2)큐 : from collections import deque 라이브러리 사용한다. 리스트에서도 함수를 이용해 큐 자료구조                       이용가능하지만, deque에 비해 시간복잡도가 높다.

 

@재귀함수 - 재귀함수는 스택에 계속 쌓이기때문에 스택자료구조를 이용해야한다면 재귀함수를 구현하면 된다.

재귀함수는 스택 자료구조에 들어갔다가 나오는 것과 같다.

 

@

@DFS

 

@너비 우선 탐색

@문제1

* 그래프 탐색문제 - 연결된 노드들을 탐색하여 방문처리 하는것!! *

 

 

@문제2

한칸씩의 거리가 같을때 최단거리탐색 - BFS

- 첫 노드 que에 넣고 꺼내서 연결된 노드들 방문하여 +1 해주고, que에 넣기. 그다음 que에 담긴 첫요소를 또 꺼내서 그와 연결된 노드들 방문해서 +1 해주고 que에 담기 반복!!

출처 : 유튜브 - 동빈나 : https://www.youtube.com/c/dongbinna