DFS 개념

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

예제

image
탐색 순서 : 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를 노드에 따라 잘 정리하는 것이 중요하다!
  • 재귀함수가 뽀인트!

댓글남기기