[Algorithm] 깊이 우선 탐색(DFS)은 뭐야?

깊이 우선 탐색 DFS는 Depth-First Search의 약자이고, 깊이를 우선으로 탐색하는 알고리즘이다. 또한 DFS는 하나의 노드를 시작으로 다수의 노드를 방문하는 그래프 탐색의 한 유형이다.

 

이때 그래프는 노드와 간선으로 표현되고 노드는 하나의 원소, 간선은 원소와 원소를 연결하는 선이다.

 

다음은 깊이 우선 탐색의 과정을 그림으로 나타낸 것이다. 초록색은 최상단 노드, 파란색은 방문 처리된 노드를 표현한다.

깊이 우선 탐색 1번째

위의 그림에서는 시작 노드인 '1'을 스택에 삽입하고 방문 처리하고 최상단 노드 처리를 한다.

 

깊이 우선 탐색 2번째

최상단 노드 '1'의 인접 노드인 '3'을 스택에 넣고 방문 처리를 하고 최상단 노드 처리를 한다.

 

깊이 우선 탐색 3번째

최상단 노드인 '3'의 인접 노드 '4'와 '5' 중에 가장 작은 노드 '4'를 스택에 넣고 방문 처리를 한다.

 

깊이 우선 탐색 4번째

최상단 노드인 '4'에 방문하지 않은 인접 노드가 존재하지 않기 때문에 스택에서 '4'를 제거한다.

 

깊이 우선 탐색 5번째

스택의 최상단 노드인 '3'에 방문하지 않은 인접 노드 '5'를 스택에 넣고 방문 처리를 한다.

 

깊이 우선 탐색 6번째

최상단 노드인 '5'의 인접 노드 '2'를 스택에 넣고 방문 처리를 한다.

 

깊이 우선 탐색 7번째

최상단 노드인 '2'에 방문하지 않은 인접 노드가 존재하지 않기 때문에 스택에서 '2'를 제거한다.

 

깊이 우선 탐색 8번째

깊이 우선 탐색 7번째에서의 과정을 반복하면 스택은 비워지고 모든 노드를 방문하게 된다. 결과적으로 노드의 방문 순서는 1 - 3 - 4 - 5 - 2가 된다.

 

위에서 설명한 깊이 우선 탐색을 파이썬 코드로 나타내면 다음과 같다.

 

def dfs(graph, v, visited):
  visited[v] = True
  print(v, end=' ')
 
  for i in graph[v]:
    if not visited[i]:
      dfs(graph, i, visited)
 
graph = [
  [],
  [3],
  [5],
  [4,5],
  [3],
  [2,3]
]
 
visited = [False] * 6
dfs(graph,1,visited)

 

graph에는 각 노드의 인접 노드의 정보를 넣어주었고 재귀 함수를 사용하여 코드가 간결하게 작성된다.

 

참고자료

이것이 취업을 위한 코딩 테스트다 with 파이썬