[c++/알고리즘] BFS :: 너비우선탐색의 개념

0. BFS란?

 i. Breadth-First Search, 너비 우선 탐색을 말한다.

모든 경로를 탐색하는 문제에서,

각 경로를 깊게 방문하지 않고

 넓게 방문할거라는 느낌만 우선 가져보자~

 

ii. 모든 경우의 수를 다 훑는 알고리즘이다. ( 정답을 찾을때까지 )

모든 경우의 수를 다 탐색하는 알고리즘에는 DFS 와  BFS 가 있다.

 

깊이 우선 탐색(Depth-First Search)는 한 경로에 대한 탐색을 우선 완료한 다음 다른 경로를 탐색하지만,

 

너비 우선 탐색은 경로상 어느 정점(node)에서 다음에 방문할 수 있는 모든 경우의 노드를 전부 방문하고, 

그 다음 단계로 넘어간다.

(따라서 내가 이해한 바로는 몇번째 방문할 노드인지에 따라 각 노드에 Hierarchy(계층 수준)이 부여되기도 한다.

같은 hierarchical depth의 노드들을 전부 방문한 다음에 다음 깊이로 들어간다.)

 

그리고 한 노드에서 방문해야할 다음 노드가 여러개일때는, 가장 먼저 입력된 정점부터 방문하기로 한다.

 

따라서 그 레벨에서 다음 방문한 노드들을 FIFO 자료구조인 Queue 로 저장한다.

 

이렇게 이야기하면 이해가 잘 안되니까~ 나중에 3번에서 예시를 살펴 보자!!

 

 

1.  BFS 의 응용

깊게 탐색하지 않고 넓게 탐색하는 BFS 는 최단경로탐색에 유리하다.

만약 노드별 가중치가 같다면, 몇번째 방문했는지가 바로 거리를 나타낼 수 있다.

그러므로 가장 적은 회차에 목적 노드에 방문한 경로가 최단 경로일 것이다. 

 

n 번째 탐색에서 이미 목적지에 도달했다면  n+1 번째는 굳이 탐색하지 않아도 된다는 뜻이다. 

 

 

반면 DFS 는 어떤 한 경로를 도착지까지 완수 한 다음에 다른 경로로 넘어간다.

 

정답 최단거리가  n임에도 불구하고,  n+10, n+12 짜리 경로들을 전부 탐색한 후에 정답을 알 수 있다.

 

심지어 n짜리 경로를 만나도 탐색을 멈추지 못한다. 왜냐하면 정답이  n-1 일수도 있기 때문이다. 

 

가장 짧은 경로는 모든 경로 탐색을 마쳐야만 알 수 있다.

 

 

따라서  BFS는  DFS에 비해 최단 경로 찾는 문제에서 탁월한 장점을 갖고 있다. 

 

2.  BFS의 장점과 단점

 장점 

출발노드에서 목표노드까지 최단 길이 경로를 보장한다.

 

단점

- 경로가 매우 길 경우, 탐색 가지가 급격히 증가함에 따라, 보다 많은 기억 공간을 필요로 하게 된다.

- 해가 존재하지 않는 경우, 유한 그래프(finite graph)의 경우 모든 그래프를 탐색한 후에 실패로 끝난다.

- 해가 존재하지 않는 경우, 무한 그래프(infinite graph)의 경우 결코 해를 찾지도 못하고 탐색을 끝내지도 못한다. 

 

 

3. BFS  예시

 

 

위와 같은 그래프에서 1번부터 너비우선탐색(BFS)를 한다면 

 

 level 1. 1번 노드 탐색

 

 

 

 

 

 

 

 

level 2.  2,4,5번 노드를  fifo(큐)에  enque

 

 

 1번 노드 다음으로 방문할 수 있는 모든 노드는 2번, 4번, 5번 노드이며

우리는 FIFO 방식으로 접근한다.

 

따라서 2번 노드 방문 (큐에 2번 노드의 다음노드인 3을 enque)

-> 4번 노드 방문(큐에 4번 노드의 다음 노드인 3,6을 enque해야한다. 그런데 3은 이미 있으니 6만 enque)

-> 5번 노드 방문(5번 노드의 다음 노드인 6을 enque해야하는데 이미 enque 돼있음)

 

 

level 3.  

큐에 있던 3, 6번 노드를 같은 방식으로 순회

3번 노드 방문 (다음 노드인 7을 que에 enque)

-> 6번 노드 방문

 

 

level 4. 마지막으로 큐에 남아 있던 7번 노드 방문!

1,2,4,5는 이미 방문했으므로 다시 방문하지 않는다.

 

 

4. BFS  예시로부터 성찰

1. 다음 방문할 노드는 큐로 관리한다.

2. 방문했던 노드는 방문 표시를 하여 큐에 중복으로 추가하지 않도록 한다.

 

 

 

 

cf) BFS랑 DFS 비교

🥊 DFS vs BFS 정리

항목DFSBFS

구조	스택(재귀)	큐
탐색방식	깊이 우선	너비 우선
장점	구현 간단	최단거리 탐색에 유리
단점	최단거리X	메모리 많이 먹을 수 있음