탐색이란

많은 양의 데이터 중에서 원하는 데이터를 찾는 과정
그래프 탐색 알고리즘 -> DFS, BFS

스택 큐 재귀함수

• 스택은 박스 쌓기에 비유
  • 나중에 들어온 것이 먼저나가는 후입선출 구조
• 큐는 대기줄에 비유
  • 먼저 온 사람이 먼저 나가는 선입선출 구조
• 재귀함수는 : 자기 자신을 다시 호출하는 함수

그래프 탐색

• BFS
• DFS

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

• 개념
  • 루트 노드에서부터 시작해서 인접한 노드를 먼저 탐색하는 방법
• 사용법
  • 현재 노드에 가까운 노드를 모두 저장해놓고 순서대로 방문해야하기 때문에
    • 스택 자료구조가 아닌
    • 큐 자료구조를 사용한다.
    • 선입선출 방법 활용 -> 큐

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

• 개념

  • 한 노드를 시작으로 인접한 다른 노드를 재귀적으로 탐색해가고 끝까지 탐핵하면 다시 위로 와서 다음을 탐색하여 검색한다.

• 사용법

  • 구현 : 스택, 재귀함수
  • 더 이상 방문할 노드가 없을때 마지막 분기점으로 돌아오는 로직을
    • 스택
    • 재귀함수 구현

  너비우선탐색 과넝(BFS)

• (처음) 시작 정점을 큐에 삽입하고 방문처리한다

• 큐에서 하나의 노드를 꺼낸다

• 꺼낸 노드와 인접한 노드 중 방문하지 않은 노드를 큐에 삽입하고 방문처리한다.

• 위 2개의 과정을 반복한다 (큐가 빌때까지)

  깊이우선탐색 과정(DFS)

• 스택

  • 탐색을 시작할 때 첫번째 노드를 스택에 삽입한다.(방문처리한다)
  • 스택에 삽입된 최상단 노드 주변에 방문하지 않았던 인접노드가 있으면, 해당 노드를 스택에 삽입하고 방문처리한다.
  • 최상단 노드에 인접한 노드가 없으면, 스택에 최상단 노드를 꺼낸다.

• 재귀

  • base condition : 파라미터로 넘어온 노드가 이미 방문한 노드라면 리턴
  • 파라미터로 넘어온 노드가 방문하지 않은 노드라면 방문표시를 한다.
  • 인접한 노드에 대해 재귀적으로 함수를 호출하며 탐색을 진행한다.