2. DFS(Depth-Find-Search) : 깊이 우선 탐색

DFS(Depth-Find-Search)

깊이 우선 탐색

 

지난 시간 BFS에 이어 오늘은 DFS에 대해 알아보려고 한다.

DFS는 Depth-Find-Search로 깊이 우선 탐색이다. BFS와 다르게 DFS는 깊이를 우선적으로 탐색한다. 즉 최대 깊이까지 재귀적으로 이동한 후 최대 깊이에 도달한 경우 옆으로 이동한다. 또한 BFS에서는 Queue를 사용했다면 DFS에서는 Stack을 사용한다. 이 Stack에 저장된 값이 우리가 원하는 DFS의 탐색 순서이다.

 

알고리즘 동작 방식 다음과 같다.

1. 특정 정점이 아직 방문하지 않은 정점인 경우 이를 방문처리 해준다.

2. 해당 정점과 연결된 다른 정점에 대해 위 과정을 반복한다.

 

다음과 같은 그래프가 주어졌을 때 DFS를 적용해보자.

 

 

① 시작 정점을 8이라고 가정하자. 아직 방문하지 않은 정점이므로, 이를 방문처리 해준다.

Visit

8

 

② 8과 연결된 1과 2를 방문 여부를 확인하고, (오름차순으로 정렬되어 있으므로 1부터 방문한다.) 이를 방문처리 해준다.

Visit

8

1

 

③ 1과 연결된 3과 5의 방문 여부를 확인하고, 이를 방문처리 해준다.

3과 연결된 다른 정점이 없으므로 5로 넘어가고, 이를 방문처리 해준다.

Visit

8

1

3

5

 

④ 5와 연결된 7과 9의 방문 여부를 확인하고, 이를 방문처리 해준다.

7과 연결된 다른 정점이 없으므로 9로 넘어가고, 이를 방문처리 해준다.

9와 연결된 다른 정점이 없으므로 2로 넘어가고. 이를 방문처리 해준다.

Visit

8

1

3

5

7

9

2

 

⑧ 위 과정이 종료되면 Visit에 저장된 정점의 순서가 DFS이다.

Visit

8

1

3

5

7

9

2

6

4

DFS 탐색 순서는 여러가지가 나올 수 있다.

필자는 간선 정보를 저장할 때 오름차순으로 정렬하는 방식을 택했다.

 

위의 개념을 파이썬으로 구현해보았다.

 

위에서 언급한 그래프로 입력 값을 주면 이론상으로 구한 답과 동일한 것을 볼 수 있다.

 

[Input]

9 8 8  # 정점의 개수, 간선의 개수, 시작 정점
8 1
8 2
1 5
1 3
5 7
5 9
2 6
6 4

 

[Output]

 

충남대학교 컴퓨터공학과 이영석 교수님의 알고리즘 수업과 동빈나의 유튜브 강좌(youtu.be/l0Rsu7dziws)를 참고했습니다.