DFS 공부

DFS 개념

• 깊이 우선
• 뿌리의 뿌리의 뿌리의 뿌리… 를 찾아서..!
• 스택을 이용!
• 재귀함수 이용!

예제

탐색 순서 : 1->2->7->6->8->3->4->5

idea

• 현재노드 일단 방문 체크
• graph[현재노드] 에서 방문 안한애 있으면 dfs 실행
• graph는 크기 순으로 정리가 잘되어있음
• 반복에서 하는 일 : 담기(스택담기), 방문처리, 출력하기
• 담기(스택담기) : graph[현재노드]에서 방문한적 없으면 방문처리하고 담기
• 방문처리 : graph[현재노드]에서 방문한적 없으면 방문처리
• 출력하기 : 스택에서 맨 상단 꺼내서 현재노드로 설정하고 출력하기 = 방문처리하고 출력하기 (방문하기와 출력이 동시에 이루어짐)
• 순서 : 담기& 출력하기& 방문하기 동시에 이루어짐 순서에 영향 없음

def dfs(graph,v,visited): #v는 현재노드
  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]
]
visited = [False]*9

dfs(graph,1,visited)

point

• graph를 노드에 따라 잘 정리하는 것이 중요하다!
• 재귀함수가 뽀인트!