Python DFS(Depth-First Search)

코딩테스트 연습 DFS

[이것이 취업을 위한 코딩테스트다 with 파이썬]을 기반으로 작성하였습니다.

DFS = Depth-First Search 로 스택 자료구조에 기초한다. 실제로는 스택을 쓰지 않아도 되며, 데이터 개수가 N일 때 O(N)의 시간이 소요된다.

알고리즘

• 최상단 노드에서 시작하여 가장 깊숙한 노드가 닿을 때까지 탐색한다.
• 재귀 함수를 이용하면 간단하게 구현 가능하다.

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 = [
         [],
         [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