[알고리즘] BFS 그래프 탐색

BFS란?

• BFS(Breadth-First Search, 너비 우선 탐색 )은 그래프 탐색 알고리즘이다.
• 시작 정점에서 가장 가까운 정점을 방문하고 멀리 떨어진 정점을 나중에 방문하는 방식으로 탐색한다

BFS 탐색 과정?

• A를 탐색하고 B와 C를 탐색 리스트에 넣는다. 탐색 리스트 = [B, C] 
• 탐색리스트에서 첫 번째 요소 B를 탐색하고 D를 탐색 리스트에 넣는다. = [ C, D ] 
• 탐색리스트에서 첫번째 요소 C를 탐색하고 E를 탐색 리스트에 넣는다. = [ D, E ]
• 탐색리스트에서 첫번째 요소 D를 탐색하고 탐색 결과가 없어서 넘어간다. = [ E ]
  
• 탐색리스트에서 첫번째 요소 E를 탐색하고 탐색 결과가 없어서 넘어간다. = []

BFS의 등장 배경

• A에서 E까지 가는 최단 경로를 찾고 싶다면 어떻게 할 것인가? 
• 탐색 리스트에 넣을때가 바로 탐색한 횟수를 카운트하면 알 수 있다. 
• 1. A를 탐색하고 B와 C를 탐색 리스트에 넣는다. 탐색 리스트 = [B, C]  1회 
  2. 탐색리스트에서 첫번째 요소 B를 탐색하고 D를 탐색 리스트에 넣는다. = [ C, D ] 2회 
  3. 탐색리스트에서 첫번째 요소 C를 탐색하고 E를 탐색 리스트에 넣는다. = [ D, E ] 3회 
  4. 탐색리스트에서 첫번째 요소 D를 탐색하고 탐색 결과가 없어서 넘어간다. = [ E ]
     
  5. 탐색리스트에서 첫번째 요소 E를 탐색하고 탐색 결과가 없어서 넘어간다. = []
• 총 3회만에 갈 수 있다는 것을 알 수 있다.

BFS를 활용하기

• 알고리즘 문제로 풀어보기
  

  2178번: 미로 탐색

정리 및 마무리 

• BFS를 사용하면 최단 거리를 알 수 있다.