#44. Algorithm34_python) DFS(깊이 우선 탐색) : Depth-First-Search

DFS : Depth-First-Search 깊이 우선 탐색

• 그래프에서 깊은 부분을 우선적으로 탐색하는 알고리즘
  • 특정한 경로로 탐색하다가 특정한 상황에서 최대한 깊숙이 들어가서 노드를 방문한 후, 다시 돌아가 다른 경로로 탐색하는 알고리즘
• 동작 과정
  • 1) 탐색 시작 노드를 스택에 삽입하고 방문 처리를 한다.
  • 2) 스택의 최상단 노드에 방문하지 않은 인접 노드가 있으면, 그 인접 노드를 스택에 넣고 방문 처리를 한다. 방문하지 않은 인접 노드가 없으면 스택에서 최상단 노드를 꺼낸다.
  • 3) 2번의 과정을 더 이상 수행할 수 없을 때까지 반복한다.

*  방문 처리 : 스택에 한 번 삽입되어 처리된 노드가 다시 삽입되지 않게 체크하는 것을 의미. 방문 처리를 함으로써 각 노드를 한 번씩만 처리 가능

 

** DFS의 기능을 생각하면 순서와 상관없이 처리해도 되지만, 코딩 테스트에서는 번호가 낮은 순서부터 처리하도록 명시하는 경우가 종종 있음. 따라서 관행적으로 번호가 낮은 순서부터 처리하도록 구현하는 편

 

• DFS는 스택 자료구조에 기초한다는 점에서 구현이 간단
• 탐색을 수행함에 있어서 데이터의 개수가 N개인 경우 O(N)의 시간이 소요
• DFS는 스택을 이용하는 알고리즘이기 때문에 실제 구현은 재귀 함수를 이용했을 때 매우 간결하게 구현 가능

 

탐색할 그래프

 

# 각 노드가 연결된 정보를 리스트 자료형으로 표현(2차원 리스트)

graph = [
  [],
  [2, 3, 8],
  [1, 7],
  [1, 4, 5],
  [3, 5],
  [3, 4],
  [7],
  [2, 6, 8],
  [1, 7]
]

DFS 구현

# DFS 함수 정의
def dfs(graph, v, visited):
    # 현재 노드를 방문 처리
    visited[v] = True
    print(v, end=' ')
    # 현재 노드와 연결된 다른 노드를 재귀적으로 방문
    for i in graph[v]:
        if not visited[i]:
            dfs(graph, i, visited)

# 각 노드가 연결된 정보를 리스트 자료형으로 표현(2차원 리스트)
graph = [
  [],
  [2, 3, 8],
  [1, 7],
  [1, 4, 5],
  [3, 5],
  [3, 4],
  [7],
  [2, 6, 8],
  [1, 7]
]

# 각 노드가 방문된 정보를 리스트 자료형으로 표현(1차원 리스트)
visited = [False] * 9

# 정의된 DFS 함수 호출
dfs(graph, 1, visited)


>>>
1 2 7 6 8 3 4 5

 

---

<참조>

• 이것이 취업을 위한 코딩 테스트다 with 파이썬(나동빈, 한빛미디어)