[알고리즘] DFS(깊이 우선 탐색) 파이썬

[알고리즘] BFS(넓이 우선탐색) 파이썬 구현 , 파이썬으로 그래프 노드 표현하기

 

# 내용

BFS와 같이 탐색을 하지만, DFS는 말 그대로 깊이 우선탐색이다. 노드들을 계속 타고 타고 타고 들어가는 것이라고 생각하면 된다.

재귀함수로도 구현이 가능하다는 생각이 들었다. 근데 재귀로 짜면 끝에서부터 찾아오는 느낌이 될거 같다. 물론 구현은 가능하겠지만, 적합하지는 않을거 같다는 생각이 들었다.

BFS와 매우 유사하지만, 방문해야할 노드들을 스택으로 표현하냐 큐로 표현하냐에 따라서 달라진다. 

스택으로 표현하는 이유는 간단하다. 내가 깊숙한 곳 까지 들어갔는데, 다시 뒤돌아갈 곳을 알아야 하기 때문이라고 생각하면 쉽다. 마치 빵조각을 하나씩 떨어뜨리면서 이동하다가 갈 길이 없으면 다시 빵을 주으면서 돌아온길을 찾아가는 것이다.

 

# 사용된 그래프

# 코드

# DFS ( 깊이 우선탐색 )

def make_graph() :
  graph = dict()
  graph["A"] = ["B","C","D"]
  graph["B"] = ["A","E"]
  graph["C"] = ["A"]
  graph["D"] = ["A","F","G"]
  graph["E"] = ["B","H"]
  graph["F"] = ["D","I","J"]
  graph["G"] = ["D"]
  graph["H"] = ["E"]
  graph["I"] = ["F"]
  graph["J"] = ["F"]
  print(f"make OK {graph}")
  return graph

def dfs(graph,start_node) :
  queue_visited = list()
  stack_will_visit = list()
  # 뽑기 -> 인접노드 방문예정 스택에 추가 -> 방문표시
  cur_node = start_node
  stack_will_visit.extend(graph[cur_node])
  queue_visited.append(cur_node)

  while stack_will_visit :
    cur_node = stack_will_visit.pop()
    print(f"queue_visited : {queue_visited}",end="")
    print(f" stack_will_visit : {stack_will_visit}",end="")
    print(f" cur_node : {cur_node}")
    if cur_node not in queue_visited :
      stack_will_visit.extend(graph[cur_node])
      queue_visited.append(cur_node)
  return queue_visited


if __name__ == '__main__':
  graph = make_graph()
  answer = dfs(graph,"A")
  print(answer)

 

# 참고

 

# .

내가 알고리즘이나 자료구조를 심도있게 공부해본게 아니지만, 지금까지는 학교 수업에 맞춰야 했기때문에 C++로 풀고 구현했었는데, 이게 파이썬으로 하니까 정말 신세계다. 자잘한 것을 신경 안써도 되는 느낌이다.

최고👍