[DS] DFS 구현 - Python

def dfs(graph, start_node):
  visited = set() # 중복 탐색 방지
  traversal = []  # 방문 순서 저장
  stack = [start_node]
  # 1. curr = stack.pop()
  # 2. 만약 curr이 visited에 없다면 visited.add(curr)
  # 3. curr과 이웃한 노드 모두 stack에 넣기
  while stack:
    curr = stack.pop()
    
    if curr not in visited:
      visited.add(curr)
      traversal.append(curr)
      for neibor in graph[curr]:
        stack.append(neibor)
        
  return traversal
  
graph = {
  'A': ['B', 'C'],
  'B': ['D','E'],
  'C': ['F'],
  'D': [],
  'E': ['F'],
  'F': []
}

print(dfs(graph, 'A'))