깊이우선탐색(DFS, Depth-First Search)

인프런에서 김태원님의 '파이썬 알고리즘 문제풀이'강의를 듣고 있다.
리트코드 사이트와 '파이썬 알고리즘 인터뷰' 책을 병행하여 보던 중,, 그 전 기초단계의 필요성을 깨닫고 수강하고 있다.

깊이우선탐색 vs 넓이우선탐색

깊이우선탐색은 한 분기가 끝날때까지 파고 조사한다.
넓이우선탐색은 해당 노드에서 가장 인접한 노드부터 조사한다.

트리에서 DFS의 탐색순서

순서 : 1 > 2 > 4 > 2 > 5 > 2 > 1 > 3 > 6 > 3 > 7

DFS 에는 전위, 중위, 후위순회방식이 있다.

전위순회방식 출력(부좌우) : 1 > 2 > 4 > 5 > 3 > 6 > 7
중위순회방식 출력(좌부우) : 4 > 2 > 5 > 1 > 6 > 3 > 7
후위순회방식 출력(좌우부) : 4 > 5 > 2 > 6 > 7 > 3 > 1
* 부는 부모, 좌우는 자식의 좌우를 뜻한다

세 방식 모두 기본 탐색순서를 따르지만 출력되는 순서가 다르다.
전위는 먼저 출력실행 후 다음 타겟을 찾는다.
중위는 좌측탐색 후 출력, 부모 출력 후 다시 우측탐색
후위는 좌측, 우측, 부모 순서이다.

코드로 보기

트리에서 보면 좌측은 부모*2, 우측은 부모*2+1이다.
재귀함수이므로 종료점을 꼭 설정해준다.

def DFS(n):
  if n > 7:
    return
  else:
    print(n) # 처리할 문(여기서는 print)이 여기 있으면 전위, 가운데 있으면 중위, 끝에 있으면 후위
    DFS(n*2)
    DFS(n*2 + 1)