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

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

그래프로 표현된 모든 자료를 빠짐없이 탐색하는 알고리즘

stack과 재귀를 이용하여 구현

 

 

DFS 진행 과정

1. 시작 정점 v를 결정하여 방문

 

2. 정점 v에 인접한 정점 중에서

      ( 1 ) 방문하지 않은 정점 w가 있으면, 정점 v를 스택에 push -> 정점 w에 방문

              v = w로 바꾸고 다시 반복

      ( 2 ) 방문하지 않은 정점이 X -> 탐색의 방향을 바꾸기 위해 스택을 pop -> 가장 마지막에

              방문한 정점을 다시 v로 바꾸고 반복

              v = stack.pop()

 

3. 스택이 공백이 될 때까지 2를 반복

 

 

 

 

DFS 예시 

좌표     A B C D E F G 

visited  F F F F F F F

stack 

 

1. A 출발

좌표     A  B  C  D  E  F  G

visited  T  F  F  F  F  F  F

stack    

 

2. A -> B

좌표     A  B  C  D  E  F  G

visited  T  T  F  F  F  F  F

stack    A  

 

3. B -> D

좌표     A  B  C  D  E  F  G

visited  T  T  F  T  F  F  F

stack    A  B  

 

4. D -> F

좌표     A  B  C  D  E  F  G

visited  T  T  F  T  F  T  F

stack    A  B  D 

 

5. F -> E

좌표     A  B  C  D  E  F  G

visited  T  T  F  T  T  T  F

stack    A  B  D  F 

 

6. E -> C

좌표     A  B  C  D  E  F  G

visited  T  T  T  T  T  T  F

stack    A  B  D  F  E

 

# 방문을 하지 않은 곳이 없어서 다시 뒤로 돌아감

7. C -> E

좌표     A  B  C  D  E  F  G

visited  T  T  T  T  T  T  F

stack    A  B  D  F  E

 

8. E -> F

좌표     A  B  C  D  E  F  G

visited  T  T  T  T  T  T  F

stack    A  B  D  F

 

8. F-> G 

좌표     A  B  C  D  E  F  G

visited  T  T  T  T  T  T  T

stack    A  B  D  F

 

-> 남은 stack을 전부 pop하며, 방문하지 않은 인접정점들이 있는지 체크

완성된 깊이 우선 탐색 경로

 

 

DFS 활용 문제 및 코드

[SWEA] 4871 그래프 경로 -python (tistory.com)

[SWEA] 4871 그래프 경로 -python