깊이 우선 탐색(DFS)

Python으로 배우는 자료구조와 알고리즘

Miriam Antona

Software engineer

트리/그래프 순회

  • 모든 노드 방문 과정
  • 깊이 우선 탐색(DFS)
  • 너비 우선 탐색(BFS)
Python으로 배우는 자료구조와 알고리즘

깊이 우선 탐색 - 이진 트리

  • 중위(In-order)
  • 전위(Pre-order)
  • 후위(Post-order)
Python으로 배우는 자료구조와 알고리즘

중위 순회

  • 순서: 왼쪽
Python으로 배우는 자료구조와 알고리즘

중위 순회

  • 순서: 왼쪽 -> 현재
Python으로 배우는 자료구조와 알고리즘

중위 순회

  • 순서: 왼쪽 -> 현재 -> 오른쪽

이진 탐색 트리에서 중위 순회의 그래픽 표현.

Python으로 배우는 자료구조와 알고리즘

중위 순회

  • 순서: 왼쪽 -> 현재 -> 오른쪽

이진 탐색 트리에서 중위 순회의 그래픽 표현.

Python으로 배우는 자료구조와 알고리즘

중위 순회

  • 순서: 왼쪽 -> 현재 -> 오른쪽

이진 탐색 트리에서 중위 순회의 그래픽 표현.

Python으로 배우는 자료구조와 알고리즘

중위 순회

  • 순서: 왼쪽 -> 현재 -> 오른쪽

이진 탐색 트리에서 중위 순회의 그래픽 표현.

Python으로 배우는 자료구조와 알고리즘

중위 순회

  • 순서: 왼쪽 -> 현재 -> 오른쪽

이진 탐색 트리에서 중위 순회의 그래픽 표현.

Python으로 배우는 자료구조와 알고리즘

중위 순회

  • 순서: 왼쪽 -> 현재 -> 오른쪽

이진 탐색 트리에서 중위 순회의 그래픽 표현.

Python으로 배우는 자료구조와 알고리즘

중위 순회

  • 순서: 왼쪽 -> 현재 -> 오른쪽

이진 탐색 트리에서 중위 순회의 그래픽 표현.

Python으로 배우는 자료구조와 알고리즘

중위 순회

  • 순서: 왼쪽 -> 현재 -> 오른쪽

이진 탐색 트리에서 중위 순회의 그래픽 표현.

Python으로 배우는 자료구조와 알고리즘

중위 순회

  • 순서: 왼쪽 -> 현재 -> 오른쪽

이진 탐색 트리에서 중위 순회의 그래픽 표현.

Python으로 배우는 자료구조와 알고리즘

중위 순회

  • 순서: 왼쪽 -> 현재 -> 오른쪽

이진 탐색 트리에서 중위 순회의 그래픽 표현.

Python으로 배우는 자료구조와 알고리즘

중위 순회

  • 순서: 왼쪽 -> 현재 -> 오른쪽

이진 탐색 트리에서 중위 순회의 그래픽 표현.

Python으로 배우는 자료구조와 알고리즘

중위 순회

  • 순서: 왼쪽 -> 현재 -> 오른쪽

이진 탐색 트리에서 중위 순회의 그래픽 표현.

Python으로 배우는 자료구조와 알고리즘

중위 순회

  • 순서: 왼쪽 -> 현재 -> 오른쪽

이진 탐색 트리에서 중위 순회의 그래픽 표현.

Python으로 배우는 자료구조와 알고리즘

중위 순회

  • 순서: 왼쪽 -> 현재 -> 오른쪽

이진 탐색 트리에서 중위 순회의 그래픽 표현.

Python으로 배우는 자료구조와 알고리즘

중위 순회

  • 순서: 왼쪽 -> 현재 -> 오른쪽

이진 탐색 트리에서 중위 순회의 그래픽 표현.

Python으로 배우는 자료구조와 알고리즘

중위 순회

  • 순서: 왼쪽 -> 현재 -> 오른쪽

이진 탐색 트리에서 중위 순회의 그래픽 표현.

Python으로 배우는 자료구조와 알고리즘

중위 순회

  • 순서: 왼쪽 -> 현재 -> 오른쪽

이진 탐색 트리에서 중위 순회의 그래픽 표현.

Python으로 배우는 자료구조와 알고리즘

중위 순회

  • 순서: 왼쪽 -> 현재 -> 오른쪽

이진 탐색 트리에서 중위 순회의 그래픽 표현.

Python으로 배우는 자료구조와 알고리즘

중위 순회 - 구현

  • 순서: 왼쪽 -> 현재 -> 오른쪽
def in_order(self, current_node):

  if current_node:

    self.in_order(current_node.left_child)

    print(current_node.data)

    self.in_order(current_node.right_child)


my_tree.in_order(my_tree.root)

10
20
22
65
68
70
75

이진 탐색 트리의 그래픽 표현.

  • 복잡도: $O(n)$
    • $n$ -> 노드 수
Python으로 배우는 자료구조와 알고리즘

전위 순회

  • 순서: 현재
Python으로 배우는 자료구조와 알고리즘

전위 순회

  • 순서: 현재 -> 왼쪽
Python으로 배우는 자료구조와 알고리즘

전위 순회

  • 순서: 현재 -> 왼쪽 -> 오른쪽

이진 탐색 트리에서 전위 순회의 그래픽 표현.

Python으로 배우는 자료구조와 알고리즘

전위 순회

  • 순서: 현재 -> 왼쪽 -> 오른쪽

이진 탐색 트리에서 전위 순회의 그래픽 표현.

Python으로 배우는 자료구조와 알고리즘

전위 순회

  • 순서: 현재 -> 왼쪽 -> 오른쪽

이진 탐색 트리에서 전위 순회의 그래픽 표현.

Python으로 배우는 자료구조와 알고리즘

전위 순회

  • 순서: 현재 -> 왼쪽 -> 오른쪽

이진 탐색 트리에서 전위 순회의 그래픽 표현.

Python으로 배우는 자료구조와 알고리즘

전위 순회

  • 순서: 현재 -> 왼쪽 -> 오른쪽

이진 탐색 트리에서 전위 순회의 그래픽 표현.

Python으로 배우는 자료구조와 알고리즘

전위 순회

  • 순서: 현재 -> 왼쪽 -> 오른쪽

이진 탐색 트리에서 전위 순회의 그래픽 표현.

Python으로 배우는 자료구조와 알고리즘

전위 순회

  • 순서: 현재 -> 왼쪽 -> 오른쪽

이진 탐색 트리에서 전위 순회의 그래픽 표현.

Python으로 배우는 자료구조와 알고리즘

전위 순회

  • 순서: 현재 -> 왼쪽 -> 오른쪽

이진 탐색 트리에서 전위 순회의 그래픽 표현.

Python으로 배우는 자료구조와 알고리즘

전위 순회

  • 순서: 현재 -> 왼쪽 -> 오른쪽

이진 탐색 트리에서 전위 순회의 그래픽 표현.

Python으로 배우는 자료구조와 알고리즘

전위 순회

  • 순서: 현재 -> 왼쪽 -> 오른쪽

이진 탐색 트리에서 전위 순회의 그래픽 표현.

Python으로 배우는 자료구조와 알고리즘

전위 순회

  • 순서: 현재 -> 왼쪽 -> 오른쪽

이진 탐색 트리에서 전위 순회의 그래픽 표현.

Python으로 배우는 자료구조와 알고리즘

전위 순회

  • 순서: 현재 -> 왼쪽 -> 오른쪽

이진 탐색 트리에서 전위 순회의 그래픽 표현.

Python으로 배우는 자료구조와 알고리즘

전위 순회

  • 순서: 현재 -> 왼쪽 -> 오른쪽

이진 탐색 트리에서 전위 순회의 그래픽 표현.

Python으로 배우는 자료구조와 알고리즘

전위 순회

  • 순서: 현재 -> 왼쪽 -> 오른쪽

이진 탐색 트리에서 전위 순회의 그래픽 표현.

Python으로 배우는 자료구조와 알고리즘

전위 순회

  • 순서: 현재 -> 왼쪽 -> 오른쪽

이진 탐색 트리에서 전위 순회의 그래픽 표현.

Python으로 배우는 자료구조와 알고리즘

전위 순회

  • 순서: 현재 -> 왼쪽 -> 오른쪽

이진 탐색 트리에서 전위 순회의 그래픽 표현.

Python으로 배우는 자료구조와 알고리즘

전위 순회

  • 순서: 현재 -> 왼쪽 -> 오른쪽

이진 탐색 트리에서 전위 순회의 그래픽 표현.

Python으로 배우는 자료구조와 알고리즘

전위 순회

  • 순서: 현재 -> 왼쪽 -> 오른쪽

이진 탐색 트리에서 전위 순회의 그래픽 표현.

Python으로 배우는 자료구조와 알고리즘

전위 순회 - 구현

  • 순서: 루트 -> 왼쪽 -> 오른쪽
  def pre_order(self, current_node):
    if current_node:
      print(current_node.data)
      self.pre_order(current_node.left_child)
      self.pre_order(current_node.right_child)

my_tree.pre_order(my_tree.root)

65
20
10
22
70
68
75

이진 탐색 트리의 그래픽 표현.

  • 복잡도: $O(n)$
    • $n$ -> 노드 수
Python으로 배우는 자료구조와 알고리즘

후위 순회

  • 순서: 왼쪽
Python으로 배우는 자료구조와 알고리즘

후위 순회

  • 순서: 왼쪽 -> 오른쪽
Python으로 배우는 자료구조와 알고리즘

후위 순회

  • 순서: 왼쪽 -> 오른쪽 -> 현재

  • 복잡도: $O(n)$

    • $n$ -> 노드 수
Python으로 배우는 자료구조와 알고리즘

중위, 전위, 후위 순회의 활용

  • 중위(in-order)

    • BST에서 노드 값을 오름차순으로 얻을 때 사용

  • 전위(pre-order)

    • 트리 복사
    • 전위 표현식 획득

  • 후위(post-order)

    • 이진 트리 삭제
    • 후위 표현식 획득
Python으로 배우는 자료구조와 알고리즘

깊이 우선 탐색 - 그래프

  • 그래프는 순환을 가질 수 있음
    • 방문한 정점을 추적해야 함
  • 단계:
    1. 임의의 정점에서 시작
    2. 현재 정점을 방문 목록에 추가
    3. 현재 노드의 각 인접 정점에 대해
      • 이미 방문한 경우 -> 무시
      • 미방문인 경우 -> 재귀적으로 DFS 수행
Python으로 배우는 자료구조와 알고리즘

깊이 우선 탐색 - 그래프

그래프에서 깊이 우선 탐색의 그래픽 표현.

Python으로 배우는 자료구조와 알고리즘

깊이 우선 탐색 - 그래프

그래프에서 깊이 우선 탐색의 그래픽 표현.

Python으로 배우는 자료구조와 알고리즘

깊이 우선 탐색 - 그래프

그래프에서 깊이 우선 탐색의 그래픽 표현.

Python으로 배우는 자료구조와 알고리즘

깊이 우선 탐색 - 그래프

그래프에서 깊이 우선 탐색의 그래픽 표현.

Python으로 배우는 자료구조와 알고리즘

깊이 우선 탐색 - 그래프

그래프에서 깊이 우선 탐색의 그래픽 표현.

Python으로 배우는 자료구조와 알고리즘

깊이 우선 탐색 - 그래프

그래프에서 깊이 우선 탐색의 그래픽 표현.

Python으로 배우는 자료구조와 알고리즘

깊이 우선 탐색 - 그래프

그래프에서 깊이 우선 탐색의 그래픽 표현.

Python으로 배우는 자료구조와 알고리즘

깊이 우선 탐색 - 그래프

그래프에서 깊이 우선 탐색의 그래픽 표현.

Python으로 배우는 자료구조와 알고리즘

깊이 우선 탐색 - 그래프

그래프에서 깊이 우선 탐색의 그래픽 표현.

Python으로 배우는 자료구조와 알고리즘

깊이 우선 탐색 - 그래프

그래프에서 깊이 우선 탐색의 그래픽 표현.

Python으로 배우는 자료구조와 알고리즘

깊이 우선 탐색 - 그래프

그래프에서 깊이 우선 탐색의 그래픽 표현.

Python으로 배우는 자료구조와 알고리즘

깊이 우선 탐색 - 그래프

그래프에서 깊이 우선 탐색의 그래픽 표현.

Python으로 배우는 자료구조와 알고리즘

깊이 우선 탐색 - 그래프

그래프에서 깊이 우선 탐색의 그래픽 표현.

Python으로 배우는 자료구조와 알고리즘

깊이 우선 탐색 - 그래프

그래프에서 깊이 우선 탐색의 그래픽 표현.

Python으로 배우는 자료구조와 알고리즘

깊이 우선 탐색 - 그래프

그래프에서 깊이 우선 탐색의 그래픽 표현.

Python으로 배우는 자료구조와 알고리즘

깊이 우선 탐색 - 그래프

그래프에서 깊이 우선 탐색의 그래픽 표현.

Python으로 배우는 자료구조와 알고리즘

깊이 우선 탐색 - 그래프

그래프에서 깊이 우선 탐색의 그래픽 표현.

Python으로 배우는 자료구조와 알고리즘

깊이 우선 탐색 - 그래프

그래프에서 깊이 우선 탐색의 그래픽 표현.

Python으로 배우는 자료구조와 알고리즘

깊이 우선 탐색 - 그래프

그래프에서 깊이 우선 탐색의 그래픽 표현.

Python으로 배우는 자료구조와 알고리즘

깊이 우선 탐색 - 그래프

그래프에서 깊이 우선 탐색의 그래픽 표현.

Python으로 배우는 자료구조와 알고리즘

깊이 우선 탐색 - 그래프

그래프에서 깊이 우선 탐색의 그래픽 표현.

Python으로 배우는 자료구조와 알고리즘

깊이 우선 탐색 - 그래프

그래프에서 깊이 우선 탐색의 그래픽 표현.

Python으로 배우는 자료구조와 알고리즘

깊이 우선 탐색 - 그래프

그래프에서 깊이 우선 탐색의 그래픽 표현.

Python으로 배우는 자료구조와 알고리즘

깊이 우선 탐색 - 구현

def dfs(visited_vertices, graph, current_vertex):
    if current_vertex not in visited_vertices:
        print(current_vertex)
        visited_vertices.add(current_vertex)
        for adjacent_vertex in graph[current_vertex]:
            dfs(visited_vertices, graph, adjacent_vertex)
  • 복잡도: $O(V+E)$
    • $V$ -> 정점 수
    • $E$ -> 간선 수
Python으로 배우는 자료구조와 알고리즘

연습해 봅시다!

Python으로 배우는 자료구조와 알고리즘

Preparing Video For Download...