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