알고리즘 | 너비우선탐색(BFS) 정리

알고리즘 | 너비우선탐색(BFS) 정리

◼ 너비우선탐색이란?

=BFS (Breadth Fist Search)

넓이를 우선적으로 탐색 한다는 것을 의미한다.

말 그대로 시작 정점으로부터 가까운 정점을 먼저 방문하고,

멀리 떨어져 있는 정점을 나중에 방문하는 순회방법으로

두 노드 사이의 최단 경로 혹은 임의의 경로를 찾고 싶을 때 많이 사용합니다.

깊이우선탐색과는 다르게 같은 레벨을 모두 검사하고 다음 레벨로 넘어갑니다.

깊이우선탐색에 대해 배우려면 클릭

좌측의 너비우선탐색 애니메이션을 보면서 쉽게 이해해봅시다

(출처: 위키백과)

같은 레벨을 모두 확인한 후 다음 레벨로 가는 것을 알 수 있습니다.

◼ 너비우선탐색의 장단점

◾ 장점

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

◾ 단점

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

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

◽ 무한 그래프(infinite graph)의 경우에는 결코 해를 찾지도 못하고, 끝내지도 못한다.

◼ 너비우선탐색의 코드진행 (예시코드)

큐에 넣고 방문한 곳을 카운트, 체크해주는 방식입니다.

코드에 대한 설명입니다.

from http://babodocoding.tistory.com/50 by ccl(A) rewrite - 2021-12-28 01:00:15