DFS 깊이 우선탐색 (Python)

DFS란?

DFS 즉 Depth-Frist-Search는 영어를 해석한 그대로 깊이를 우선으로 탐색하는 즉 깊이 우선 탐색입니다.

깊이를 우선 탐색한다는 것은 그래프에서 한 노드에서 연결된 다른 노드들 중 한 방향의 노드에 대해서 계속 파고 들어간다는 뜻 입니다. 그림 1을 보시면 이해가 더욱 쉽습니다. 

 

그림 1

 

그림 1에서 노드 1을 시작점으로 DFS를 수행해보겠습니다. (위 예시에서 설명을 용이하게 하기 위해 낮은 숫자부터 방문한다고 가정하겠습니다.)

1번을 탐색하고 난 뒤 갈 수 있는곳은 2, 3, 7 이 있지만 낮은 숫자인 2를 탐색합니다.(탐색:  1, 2)

2번을 탐색하고 난 뒤 갈 수 있는곳은 9 가 있습니다. 9를 탐색합니다. (탐색: 1, 2, 9)

9번을 탐색하고 난 뒤 갈 수 있는곳은 3, 4가 있지만 낮은 숫자인 3을 탐색합니다. (탐색: 1, 2, 9, 3)

3번을 탐색하고 난 뒤 갈 수 있는곳이 없으므로 다시 9로 돌아온 후 4를 탐색합니다. (탐색: 1, 2, 9, 3, 4)

4번을 탐색하고 난 뒤 갈 수 있는곳이 없으므로 다시 1로 돌아온 후 7을 탐색합니다. (탐색: 1, 2, 9, 3, 4, 7)

7번을 탐색하고 난 뒤 갈 수 있는곳이 6, 8, 이 있지만 낮은 숫자인 6을 탐색합니다. (탐색: 1, 2, 9, 3, 4, 7, 6)

6번을 탐색하고 난 뒤 갈 수 있는곳이 없으므로 다시 7로 돌아온 후 8을 탐색합니다. (탐색: 1, 2, 9, 3, 4, 7, 6, 8)

8번을 탐색하고 난 뒤 갈 수 있는곳은 5가 있습니다. 5를 탐색합니다. (탐색: 1, 2, 9, 3, 4, 7, 6, 8, 5)

모든 곳을 탐색하였으므로 탐색을 종료합니다.

탐색이 되는 순서는 위와 같이 1, 2, 9, 3, 4, 7, 6, 8, 5입니다. DFS는 구현을 스택을 이용하여 합니다만 제가 공부를 했던 나동빈 님의 이것이 취업을 위한 코딩 테스트다 with Python에서는 재귀의 형태로 구현을 하였고 저도 해당 코드를 인용하기 때문에 재귀를 이용하여 구현하겠습니다.

 

---

소스코드

 

 

def dfs(graph, visited, start):
  visited[start] = True # 방문처리
  print(start, end=" ") 
  for i in graph[start]: # start와 연결되어 있는 노드 탐색 중
    if not visited[i]: # 방문하지 않은 노드가 있다면
      dfs(graph, visited, i) # 재귀적으로 호출
 
graph = [
  [],
  [2, 3, 7],
  [1, 9],
  [1, 9],
  [9],
  [8],
  [7],
  [1, 6, 8],
  [5, 7],
  [2, 3, 4]
]
visited = [False] * 10
 
dfs(graph, visited, 1)