[문제해결 알고리즘] BFS :: 너비우선탐색의 개념

0. BFS란?

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

모든 경로를 탐색할건데, 각 경로를 깊게 방문하지 않고 넓게 방문할거라는 느낌만 우선 가져보자~

 

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

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

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

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

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

그리고 한 노드에서 방문해야할 다음 노드가 여러개인데, 가장 먼저 입력된 정점부터 방문하기로 한다. (따라서 그 레벨에서 다음 방문한 노드들을 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번과 5번 노드이며

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

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

-> 4번 노드 방문(큐에 4번 노드의 다음 노드인 6를 enque)

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

 

 

 

level 3.  

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

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

-> 6번 노드 방문

 

 

 

 

 

 

 

 

 

 

 

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

 

 

 

4. BFS  예시로부터 성찰

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

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

 

 

 

 

 

  참고 : 

https://ko.wikipedia.org/wiki/%EB%84%88%EB%B9%84_%EC%9A%B0%EC%84%A0_%ED%83%90%EC%83%89