[Algorithm] BFS, DFS (with Python)

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

이 알고리즘의 핵심은 큐(Queue)를 사용하는 것

노드를 방문하면서 인접한 노드 중 방문하지 않았던 노드의 정보를 큐에 넣어 큐에 먼저 들어있던 노드부터 방문.

list 형식을 사용해 큐를 구현할 수도 있지만, list.pop(0)은 시간복잡도가 O(N)이므로 비효율적. -> collections 라이브러리의 deque를 사용. 방문하지 않았던 노드를 큐에 넣을때는 set타입을 사용.

 

DFS(Depth First Search, 깊이 우선 탐색)

이 알고리즘의 핵심은 스택(Stack)을 사용하는 것.