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

• 그래프 완전 탐색 기법 중 하나로, 그래프의 시작 노드에서 출발하여 탐색할 한 쪽 분기를 정하여 최대 깊이까지 탐색을 마친 후 다른 쪽 분기로 이동하여 다시 탐색을 수행하는 알고리즘
• 재귀 함수로 구현
  • 스택 오버플로우(stack overflow)에 유의해야 함
• stack 자료구조 활용 → LIFO 탐색
• 시간 복잡도: O(V+E)
  • V: 노드 개수
  • E: 에지 개수

깊이 우선 탐색의 핵심 이론

• 한 번 방문한 노드를 다시 방문하지 x

  • 노드 방문 여부를 체크할 리스트가 필요함
  • 이때, 그래프는 인접 리스트로 표현함

• 탐색 시 후입선출 특성을 가짐 → stack 활용

  • 스택에 노드를 삽입할 때 방문 리스트를 체크: append()
  • 스택에서 노드를 뺄 때 탐색 순서에 기록: pop()

  ⇒ 인접 노드를 방문 리스트와 대조하여 살펴봄

1) 시작 노드 정하기 및 사용할 자료구조 초기화하기

• DFS를 위해 필요한 초기 작업은 인접 리스트로 그래프 표현하기, 방문 리스트 초기화하기, 시작 노드를 스택에 삽입하기임

• ex> stack에 시작 노드를 1로 삽입 시

  

2) 스택에서 노드를 꺼낸 후 꺼낸 노드의 인접 노드를 다시 스택에 삽입하기

• pop()을 수행하여 노드를 꺼냄

• 꺼낸 노드를 탐색 순서에 기입하고 인접 리스트의 인접 노드를 스택에 삽입하며 방문 리스트를 체크

  

3) 스택 자료구조에 값이 없을 때까지 반복하기

• 앞선 과정을 스택 자료구조에 값이 없을 때까지 반복

이미 다녀간 노드는 방문 리스트를 바탕으로 재삽입하지 않기!

5-2. 너비 우선 탐색(Breadth-First Search, BFS)

• 그래프 완전 탐색 기법 중 하나로, 시작 노드에서 출발해 시작 노드를 기준으로 가까운 노드를 먼저 방문하면서 탐색하는 알고리즘