BFS와 DFS (3)/ BFS와 DFS 정의와 구현

나동빈님의 '이것이 코딩테스트다 with 파이썬'저서를 참고하며 작성하였습니다. 

코드 출처: https://github.com/ndb796/python-for-coding-test

---

▶ DFS (Depth-First Search) 란?

그래프에서 깊은 부분을 우선적으로 탐색하는 알고리즘이다. 시작노드에서 시작하여 인접한 노드들을 방문하며 가장 깊숙이 위치하는 노드에 닿을 때까지 탐색한다. 인접한 리스트가 여러개일 경우 노드의 숫자가 가장 낮은 방향으로 탐색한다. 

 

> 다음 그래프가 있을 때 DFS는 어떤식으로 탐색할까?

(설명 뒤의 []는 쌓이는 스택을 표현한 것이다)

- 1에서 탐색을 시작한다. [1]

- 연결된 노드 2,8,6중 가장 낮은 수인 2로 탐색한다. [1,2]

- 2에서 3으로 방문한다. [1,2,3]

- 3에서 7과 5중 5를 방문한다. [1,2,3,5]

- 5에서 방문하지 않은 인접노드가 없기에 5를 스택에서 꺼내고 3으로 다시 되돌아간다. [1,2,3]

- 3에서 방문하지 않은 7로 방문한다. [1,2,3,7]

- 7에서 방문하지 않은 인접노드가 없기에 다시 3로 돌아간다. [1,2,3]

- 3에서 2로, 2에서 1로 돌아간다. [1,2] -> [1]

- 1에서 8과 6중, 6으로 방문한다. [1,6]

- 6에서 4로 방문한다. [1,6,4]

- 4를 스택에서 꺼내고 6으로 돌아간후 8로 방문한다. [1,6,8]

- 남아있는 노드에 방문하지 않은 인접노드가 없으므로 모든 노드를 차례대로 꺼내면 다음 순서와 같다.

1-> 2-> 3-> 5-> 7-> 6-> 4-> 8

 

 

 

▶ DFS구현

DFS는 위에서 보았듯이 나중에 들어온 것이 먼저 나가는 스택 자료구조에 기초한다.DFS는 재귀함수를 통해 다음과 같이 구현할 수 있다. 

dfs 재귀함수를 반복하여 호출함으로써 방문하지 않은 노드들을 방문하고 모든 노드를 방문하였을 때 재귀함수의 실행이 종료된다. 

1,2,7,6,8,3,4,5는 노드가 탐색된 순서를 출력한 것이다. 

 

 

 

▶ BFS (Breadth First Search)란?

너비 우선 탐색으로 불리며 가까운 노드부터 먼저 탐색하는 알고리즘으로 큐 자료구조를 이용한다. 번호가 낮은 인접노드부터 먼저 방문한다. DFS와 달리 인접 노드 부터 먼저 큐에 삽입하고 그 후 거리가 먼 노드들에 대해 차례대로 삽입을 진행한다. 

 

> DFS와 마찬가지로 같은 그래프에 대해 BFS는 어떻게 작동할까?

- 1번부터 탐색시작한다. [1]

- 1을 제거하고 인접노드인 2,6,8이 차례대로(작은 수부터) 큐에 삽입된다. [2,6,8]

- 가장 작은 수인 2를 제거하고 인접노드인 3을 삽입한다. [6,8,3]

- 다음으로 6을 제거하고 인접노드이자 방문하지 않은 노드인 4를 삽입한다. [8,3,4]

- 8을 제거했지만 인접노드에 방문하지 않은 노드가 존재하지 않으므로 무시한다. [3,4]

- 3을 제거하고 5와 7을 삽입한다. [4,5,7]

- 모든 노드를 방문했으므로 큐에서 모든 노드들을 차례대로 꺼내고 종료된다. 

1->2->6->8->3->4->5->7 

 

 

 

▶ BFS 구현

DFS와 달리 BFS는 먼저 들어간 노드가 먼저 빠지는 큐 자료구조를 사용하기 때문에 deque를 사용하여 구현할 수 있다.

bfs에서 모든 노드들이 제거되면 해당 함수는 종료된다.