[알고리즘] 깊이/너비 우선 탐색(DFS&BFS)

Janet·2023년 4월 26일
0

Algorithm

목록 보기
167/314
  • DFS는 그래프에서 깊은 부분을 우선적으로 탐색하는 알고리즘이다.
  • DFS는 스택 자료구조 혹은 재귀함수를 이용한다.
    • Stack: 먼저 들어온 데이터가 나중에 나가는 선입후출 형식의 자료구조. (입구와 출구가 하나인 형태)
    • Recursive Function(재귀함수): 자기자신을 다시 호출하는 함수를 말한다.
  • DFS의 동작 과정
    • 탐색 시작 노드를 스택에 삽입하고 방문 처리한다.
    • 스택의 최상단 노드에 방문하지 않은 인접한 노드가 하나라도 있으면 그 노드를 스택에 넣고 방문 처리, 방문하지 않은 인접 노드가 없으면 스택에서 최상단 노드를 꺼낸다.
    • 더이상 위의 과정을 수행할 수 없을 때까지 반복한다.
  • BFS는 그래프에서 가까운 노드부터 우선적으로 탐색하는 알고리즘이다.
  • BFS는 큐 자료구조를 이용한다.
    • Queue: 먼저 들어온 데이터가 먼저 나가는 선입선출 형식의 자료구조이다. (입구와 출구가 모두 뚫려있는 터널 형태)
  • BFS의 동작 과정
    • 탐색 시작 노드를 큐에 삽입하고 방문 처리를 한다.
    • 큐에서 노드를 꺼낸 뒤에 해당 노드의 인접 노드 중에서 방문하지 않은 노드를 모두 큐에 삽입하고 방문 처리한다.
    • 더이상 위의 과정을 수행할 수 없을 때까지 반복한다.

  • 인접한 노드가 여러 개 일 수 있는데, 이때 어떤 노드부터 방문할 지를 결정하는 기준은 문제에서 요구하는 내용에 따라 달라질 수 있다.
  • 다음은 그림 예제이다.

profile
😸

0개의 댓글