BFS로 최소비용 문제 해결하기

도입

BFS 알고리즘의 목적은 그래프에서 모든 정점을 한번씩만 확인하기 위한 것입니다.

BFS가 너비우선탐색조건이라는 성질 때문에 몇가지 조건만 성립하면 최소비용 문제를 해결할 수 있습니다.

---

BFS란?

BFS 그래프 설명 참고하기

[Algorithm] 그래프란? 그래프 탐색알고리즘(DFS,BFS)

BFS는 그래프의 탐색에서 사용되는 알고리즘입니다. DFS와 동일하게 모든 정점을 한번씩만 확인할 때 사용합니다.

BFS는 너비를 우선으로 탐색하는 기능을 수행하기 때문에 최소비용 문제를 해결할 수 있습니다. BFS에 대해 좀 더 자세히 알고 싶으시면 위 링크를 확인해주시면 감사하겠습니다.

최소비용 문제를 풀 수 있는 이유?

BFS가 최소비용 문제를 해결할 수 있는 이유를 알아보겠습니다.

BFS 탐색 순서

BFS는 너비 우선 탐색이기 A에서부터 탐색을 시작하면 A -> (B,C,D) -> E -> F의 순서로 탐색을 하는 것을 알 수 있습니다.

이렇게 탐색을 하게되면 각 정점은 시작정점과 떨어진 간선의 수(n) 만큼의 위치에서 탐색하게 됩니다. 즉 A지점에서 B,C,D는 1개의 간선 너머에 있기 때문에 1번째만에 확인하였고, E는 A와 2개만큼의 간선과 떨어져 있기 때문에 2번만에 확인하고, F는 3개의 간선만큼 떨어져 있기 때문에 3번만에 확인하게 된 것입니다.

 

즉 BFS를 사용하면 확인되는 순서는 시작 정점과 떨어진 최소간선의 수가 되는 것 입니다. 따라서 시작 정점부터 최소비용의 문제를 해결할 수 있게 됩니다.

최소비용 문제를 풀기위한 조건?

가장 기본적으로 그래프로 구성될수 있어야 합니다. 그리고 시간내에 해결이 가능한지 확인하여야 합니다.

BFS의 시간 복잡도는 $O(V+E)$로 정점과 간선의 수입니다. 그런데 보통 $E > V$이므로 $O(E)$라고도 표현합니다. 그렇다면 최소비용 문제를 해결하기 전에 해당 간선의 수가 어느정도가 되는지 확인해 주어야합니다. 그래프로 구성했는데 간선의 수가 10억개가 되는 등의 일이 발생하면 이는 BFS로 해결이 불가능한 문제입니다.

그리고 모든 간선의 가중치가 동일해야합니다. 위에서 확인한 결과 BFS를 사용하면 시작정점과 떨어진 최소 간선의 수를 알 수있고 이 조건으로 최소비용 문제를 해결합니다.가중치가 동일하면 최소비용 문제를 해결하는데 간선의 수만 고려하여 주면 됩니다. 하지만 아닐 경우에는 가중치까지도 고려해주어야하기 때문에 BFS로 해결이 제한되어 다른 방법으로 해결해주어야 합니다.

 

정리하면 BFS로 문제를 해결할 수 있는지 사전에 간선의 수를 고려하고 그리고 각 간선의 가중치가 동일한지 조건을 확인해 주어야합니다.

최소비용 문제를 구현하는 방법

시작정점과 떨어진 최소간선의 수를 $P(n)$이라고 하고, $P(n-1)$을 자신을 체크한 이전 정점의 연결된 간선의 수라고 하겠습니다. 그렇다면 정점에서 연결된 정점의 수는 $P(n) = P(n-1) + 1$이 됩니다. BFS를 구현할 때 이전 정점에서 간선리스트를 확인하며 체크가 안된 정점을 Queue에 넣으며 체크합니다. 따라서, 정점을 체크할 때 항상 자신을 체크한 정점을 알 수 있기 때문에 위 식을 사용해 구현해주면 됩니다

---

마무리

1. BFS를 사용해 확인할 때 너비의 순서는 시작정점과 떨어진 최소 간선의 수가 된다.
2. 만약 간선의 가중치가 동일하고 그래프로 표현이 가능하고 간선의 수가 적당하다면 BFS로 최소비용 문제를 해결할 수 있다.

 

잘못된 정보나 궁금한점은 편하게 댓글 달아주시면 감사하겠습니다 :)