dfs 제대로 정리

단순 탐색의 방식만 달라질뿐이지 어짜피 모든 정점을 탐색하는것은 같다.

 

한마리도 bfs는 need_visited 큐와 visited큐가 있었는데

그것중 need visited 를 스택으로 바꿔주면 되는것이다.

 

동작 방식은 bfs랑 유사하다.

원래 큐에서 빼는 방식이 스택으로 뺴는 방식으로 바뀌었을뿐

그리고 중복검사도 visited 큐에 담을떄 해주는것도 똑같다.

 

스택에 넣을떄도 들어가있는 즉 연결되어있는 방향 어디로 탐색할지 상관없다 그냥 탐색하면된다.

즉 그냥 스택에 물려있는 노드들 넣어주면됨

 

그냥 진짜 큐가 스택으로 바뀐거 빼고는 다른거 하나 없음

 

바로 코드 구현으로 해보자.

 

dfs는 스택 쓴다는걸 알면되는데 스택 자체가 그냥 원래 컴퓨터 구조상 스택으로 돌아가기 떄문에

그냥 재귀만들어서 쭉열어주면 알아서 dfs 로 한다

 

from collections import deque

def dfs(graph,start_node):
    visited = list()
    need_visited = deque() #스택 정책이용

    while need_visited:
        node = need_visited.pop()
        if node not in visited:
            visited.append(node)
            need_visited.extend(graph[node])

 

그냥 코드는 bfs에서 need_visit를 스택으로 바꿔주는게 다인데 대부분 재귀로 푸는데 재귀는 어캐하는건지 또 찾아봐야겠다

 

재귀로 푸는거

 

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

이렇게 라는데 이건 문제풀면서 익숙해져야겠다