문제를 풀다보니 BFS에도 다양한 활용방법이 있다는걸 깨닫게 됐습니다. 그래서, 그 활용방법에 대해서 간단하게 정리해보려고 합니다. 활용의 범위가 애매하긴 하지만, 제가 느끼기에 이건 쫌 직관적으로 떠올리기 어려운 활용법이라고 생각한 것을 정리해볼 생각입니다.
BFS에 대한 이해도가 있다고 가정하고 쭉 정리할 생각이니, 혹시 이 글을 보는 분들 중 BFS에 대해서 모르신다면 , 먼저 이해를 하고 와주신다면 더 이해에 도움이 될 것 같습니다!
거리에 맞는 BFS 점들을 탐색하고 싶을 때
BFS에서 Queue는 시작점 기준으로 거리 순서대로 쌓이게 됩니다. 이때, 이야기하는 거리는 지나가는 간선의 갯수라고 하는게 정확할 것 같습니다.
왼쪽이 그래프라고 했을 때, 오른쪽의 BFS탐색 큐라고 한다면, 초록색 -> 노란색 ..과 같은 순으로 Queue에 쌓이게 됩니다. 이때, 그래프에서 보자면 지나간 간선의 갯수가 1개면 초록색, 2개면 노란색과 같이 간선의 갯수에 따라서 Queue에 쌓이게 됩니다.
하지만, 문제를 풀다보면, 지나온 간선의 갯수 즉, 거리에 따라서 추가적인 로직을 실행하고 싶을 때가 있습니다. 예를들어, 내가 거리가 1인 지점을 지나고 난 뒤에 , 그 중에서 가장 작은 가중치를 가진 정점을 원할 수 있습니다. 문제스럽게 만든다면, 거리가 1인 곳에서 치킨이 가장 싼 치킨집을 찾고 싶다가 될 수 있습니다.
그렇게 로직을 짜고싶을 때, 통상적으로 짤 때처럼 Queue가 비워질 때 까지라는 로직을 이용하면 안됩니다. 이미 힌트는 다 나왔는데, 눈치 채셨나요?
바로, Queue의 Size, Queue의 길이에 따라서 반복을 해주면 됩니다. 예를들어, 거리가 1인 정점들은 위의 그림에서는 3개니까, Queue에서는 3개의 정점이 한번의 Queue의 원소 POP으로 생겨나게 됩니다. 그때의 Queue size만큼 반복을 하고, 다음 정점을 쌓는걸로 로직을 분리하게 되면 거리에 따라서 로직을 추가할 수 있게 됩니다.
queue<pair<int, int>> Q;
int dist = 0;
// Q가 비워질때 까지
while (!Q.empty())
{
int curSize = Q.size();
for (int i = 0; i < curSize; i++)
{
~ 탐색 로직 ~
~ 추가로직 ~
}
}0-1 BFS
0 -1 BFS는 BFS를 그래프에 좀 더 잘 응용할 수 있게 해주는 개념이다. 사실, 2차원 맵에서 BFS를 이용하는게 BFS의 원래 모습은 아니다. BFS를 2차원 맵에서 이용할 수 있는 이유는 2차원 맵을 그래프로 연결되어 있다고 생각하자라는 걸 기반에 둔다.
위 그럼처럼, 각각의 정점에 대해서 4개의 edge와 4개의 정점이 연결되어있고, 가중치가 없다는 가정하(정확히는, 가중치가 똑같다)에 우리는 2차원 맵을 다룰 수 있게 된다고 한다.
그치만, BFS를 조금만 활용하면 가중치가 2가지인 경우에 이용할 수 있다. 가중치가 2가지인 경우는 여러의미로 나타날 수 있다. 예를들어 지금 1번에 있는 사람은 "좌우 달리기" 장인이어서, 위아래를 움직일 때는 에너지가 들고 좌우는 아무런 에너지 소모없이 달리기를 할 수 있다. 와 같이
"2가지 상황"으로 제약이 될 때, 0-1BFS를 이용할 수 있다.
물론, 가중치가 있는 그래프에서 최단거리를 구하는 방법은 다익스트라가 있기 때문에, 다익스트라를 써도되지만, 0-1 BFS를 이용하면 선형시간에 구할 수 있는 경우가 있으므로 알아두자.
응용방법은 간단하다. BFS를 탐색하는 Queue를 Deque로 바꾸어주고, 가중치가 작은(가중치가 우선순위가 높은) 건 먼저 넣어주고, 가중치가 작은 경우는 뒤로 넣어주면 된다. 아래와 같은 로직을 응용해주면 된다. if안에는 가중치에 대한 여러 조건이 들어갈 수 있으므로, 의사코드로 간단하게 표현해줬다.
deque<int> dq;
...
if(가중치가 우선순위가 높은 경우) {
dq.push_front();
}
if(가중치가 우선순위가 낮은 경우){
dq.push_back();
}
방문배열 응용시리즈
BFS 다차원 방문배열
문제를 풀 다 보면, 방문했던 점에 다른 방법으로 방문을 하게되면 , 최단거리가 바뀌는 문제들이 있다.
예를들어, 상하좌우 뿐만아니라, 어떨 때는 막 장기의 상처럼 움직인다던지, 불이 났는데 2번~3번정도는 뚫고 갈 수 있다던지 등등 방문했던 점에 또 방문을 하는 경우가 있다.
이때는, 방문배열을 여러개 만들어줘서, 각각의 상황마다 방문배열을 다르게 하는것이 유리하다. 물론, 변수를 이용해서 각각을 구분해도 되지만, 각 상황별로 모든 것을 반영하기가 쉽지 않기 때문에 주로 방문배열을 여러개 만들어주게 된다.
BFS 방문배열에 여러가지 의미담기
True/False , 거리 등으로 방문배열을 이용하는게 흔한 컨셉이지만, 방문배열을 상태의 개념으로 보고, 1이면 어떤 상태, 2이면 어떤 상태 , 3이면 어떤 상태로 나타낼 수 있다.
