알고리즘 코딩테스트 핵심이론 강의 - BFS (너비 우선 탐색)

https://www.youtube.com/watch?v=Cs8DaupoSPM

📌 BFS (너비 우선 탐색)

• 그래프를 완전 탐색 (DFS와 동일)
• 시작 노드에서 출발해 시작 노드를 기준으로 가까운 노드를 먼저 방문하면서 탐색
• 선입선출 방식으로 탐색하므로 큐를 이용해 구현
• 탐색 시작노드와 가까운 노드를 우선 탐색 하므로 목표 노다가 도착하는 경로가 여러 개 일 때 최단경로 보장

특징시간 복잡도 (노드 수 : V, 에지 수 : E)

FIFO 탐색	O(V+E)
Queue 자료구조 이용

*DNS : FILO : 먼저 들어온 DATA가 나중에 나간다
*BFS : FIFO : 먼저 들어온 DATA가 먼저 나간다

 

◾ 깊이 우선 탐색의 동작 과정

 

출처 : https://velog.io/@sukong/%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98-%EA%B0%9C%EB%85%90-%EB%84%88%EB%B9%84%EC%9A%B0%EC%84%A0%ED%83%90%EC%83%89BFS-lp8zywtn

1. BFS를 시작할 노드를 정한 후 사용할 자료구조 초기화

• 방문했던 노드를 다시 방문하지 않으므로 방문한 노드를 체크하기 위한 배열 필요
• 탐색을 위해 스택이 아닌 큐 사용
  
  

2. 큐에서 노드를 꺼낸 후 꺼낸 노드의 인접 노드를 다시 큐에 삽입

• 인접 노드를 큐에 삽입 할 때 방문 배열을 케흐하고 큐에서 꺼낸 노드를 탐색 순서에 기록
  
  

3. 큐 자료구조에 값이 없을 때까지 반복

• 큐가 비어지면 검색할 노드가 없는 것이도 BFS가 종료 됨.