우리는 그래프에서 경로를 찾는 깊이 우선 탐색 알고리즘을 살펴보았죠.
이번에는 너비 우선 탐색(Breadth First Search) 알고리즘을 알아보기로 해요.
깊이 우선 탐색 알고리즘을 스택을 이용하는 동적 프로그래밍 기법을 사용했어요.
너비 우선 탐색 알고리즘은 큐를 이용하는 탐색 방법으로 최단 경로를 찾는 알고리즘의 하나예요.
너비 우선 탐색 알고리즘은 출발지에서 가까운 경로 순으로 탐색하는 알고리즘이예요.
깊이 우선 탐색 알고리즘은 한쪽 방향으로 이동하면서 경로를 탐색했어요.
만약 막히면 이전 갈림길에서 다른 경로를로 다시 이동하면서 경로를 탐색하는 알고리즘이였죠.
이에 반해 너비 우선 탐색 알고리즘은 출발지에서의 경로가 가까운 순서로 탐색해 나가요.
이를 위해 너비 우선 탐색 알고리즘에서는 경험 정보를 큐에 보관해요.
그리고 큐에서 꺼낸 경험 정보의 마지막 방문한 정점에서 갈 수 있는 다음 경험 정보를 찾아요.
그리고 조사한 다음 경험 정보의 마지막 방문한 정점이 목적지면 바로 최단 경로예요.
만약 목적지가 아니면 다시 큐에 보관해요.
이를 반복하면 출발지와 목적지 사이의 모든 경로를 최단 경로 순으로 찾을 수 있어요.
다음은 너비 우선 탐색 알고리즘의 의사 코드예요.
너비우선탐색 알고리즘
초기 경험 정보를 생성
큐에 초기 경험 정보 Put
반복(큐가 빌 때까지)
큐에서 경험 정보를 Get
꺼낸 온 경험에서 발생할 수 있는 다음 경험 정보 조사
반복(다음 경험 정보들을 순차적으로)
조건(결론에 도달했으면)
경로 출력
그렇지 않다면
큐에 보관