알고리즘 : BFS (1) 넓이 탐색 알고리즘이란 무엇인가

알고리즘 하면 왠지 'BFS', 'DFS'가 가장 인지도가 높은 것 같다(?)

대충 알 것 같은 DFS를 뒤로 하고, BFS의 이론을 공부해보려 한다.

 

우선 둘다 그래프 탐색 알고리즘이다.

자료구조 중 가장 어렵다고 생각하는 '그래프' ..는 다음에 차차 제대로 공부하기로 하고.

원래 스키도 고급부터 타면서 배운다고, 나는 알고리즘 먼저 배우고 그래프를 공부해보려고 한다.

 

DFS와 BFS 모두 시간 복잡도는 O(N)이다.

DFS는 깊이 탐색 알고리즘, BFS는 넓이 탐색 알고리즘!

가장 간단하게 풀이하자면,

DFS → 재귀, stack

BFS → queue (deque)

 

일반적으로 DFS 보다 BFS가 조금 더 빠르다고 한다.

이런 둘의 사용 여부 구분은 크게 이러하다.

DFS → 특정 목표 node를 조회, 그래프 규모 big

BFS → 최단 경로, 그래프 규모 small

 

문제를 읽고 그래프 규모가 커질 수 있다고 생각하면 DFS, 작은 것 같다면 BFS를 사용하자!

그럼 이제 진짜 BFS에 대해 시작해보겠다.

 

---

 

 

BFS란?

root에서 인접한 node를 먼저 탐색하는 알고리즘이다.

정점에 연결된 가까운 점들부터 탐색하는 방법이기 때문에 queue로 구현할 수 있다.

 

그림으로 표현하면,

이렇다. 즉, 탐색 순서는 A → B → C → D → E → F

 

그림으로 확인하면 최단 경로를 찾는 것에 유리한 이유를 알 것 같기도 하다..(?)

두 개의 node 사이에서 최단 경로를 찾는 것이 유용해보이니까!

 

그러나.. 사실 곧바로 이해하긴 좀 어렵다.

과정을 정확히 이해하기 위한 참고 자료를 보자 ⬇️

(참고 자료 출처 : https://bbangson.tistory.com/42)

 

 

그래프로 표현한 과정이다. 이 자료로 보면 왜 BFS가 최단 경로 찾기에 특화된 알고리즘인지 단번에 이해가 간다.

확률과 통계에 자주 나오는 어릴 때 재밌게 풀던 최단 경로 문제와 어째 비슷한 그림이라서 그런가..

그리고 왜 queue를 사용하여 구현하는지도 이해가 확 간다.. ^__^!

 

 

DFS와의 공통점?

둘다 조건 속 모든 node를 조회한다. 따라서 시간 복잡도가 동일하게 O(N)인 것이다.

 

 

DFS와의 차이점?

경로의 특징을 저장해야 하거나, 자료가 많아 모든 node를 방문해야 할 때 활용하는 DFS와 달리,

BFS는 임의의 거리 혹은 경로를 구하기 위해 활용한다.

 

 

BFS를 활용하는 방법은?

DFS는 재귀를 통해 구현할 수 있고, 그게 대체적인 코드이다.

BFS는 DFS와 달리 '반복문'을 활용한다.

 

 

그런데  ... 이렇게 이론으로만 이야기하면 솔직히 100% 이해하기는 어렵다.

그냥 당장 코테부터 풀어보자는 생각이 드는 .. BFS 알고리즘 🥹

이론은 이쯤에서 멈추고 실습 단계로 Go!

 

코테를 풀면서 이해해보고 이해가 안 가면 참고하면서 공부하는게 가장 Best!일 것 같다.

그럼 다음 포스팅으로 갑니다~👋🏻

-끝-