너비 우선 탐색 (BFS, Breadth First Search)
해당 글은 공부를 하면서 적은 글이기 때문에 틀릴 수 있습니다. 참고용으로만 봐주세요~
1. 서론
너비 우선 탐색(BFS)은 주로 DFS와 함께 설명된다. DFS와 달리 깊이를 우선으로 탐색하지 않고, 너비를 우선적으로 탐색하는 알고리즘이기 때문에 주로 비교해서 설명되어 있는 편이다.
너비 우선 탐색(BFS)은 시작 노드에 인접한 노드부터 탐색하는 알고리즘이다.
해당 알고리즘은 그래프에서 모든 간선의 비용이 동일한 조건에서 최단 거리를 구하는 문제를 효과적으로 해결할 수 있는 알고리즘이다.
예시로 "미로를 빠져나가는 최단 거리(경로)"를 구하는 문제 등에서 효과적으로 활용할 수 있는 알고리즘이다.
만약 비용이 동일하지 않다면, 다른 길 찾기 알고리즘(Dijkstra 알고리즘, AStar(A*) 알고리즘 등)을 이용해야 한다.
해당 BFS를 이용해 만들었던 기능 중 하나는 포토폴리오로 게임 모작을 만들 때, ImGui를 이용해 게임 에디터 툴을 만들 때 사용했었다.
정확하게는 아틀라스 이미지를 띄우고 이미지들 중 하나를 선택하면, 자동으로 영역을 잡아주는 기능을 만들었다.
이때는 마우스로 클릭한 픽셀을 기준으로 너비 우선탐색을해 지정해둔 배경색(RGBA 중 alpha값이 0인 이라던지, 255, 0, 255 색인 마젠타 색이라던지)을 만나면 좌상단과 우하단을 기록해 잘라주는 식으로 만들었다.
(이전에는 직접 드래그로 자르거나 계산해 사용했었어 불편했다. 하지만 이 기능도 불완전 한 것이 하나의 애니메이션 프레임에 서로 떨어진 (예를 들어 이팩트) 이미지들은 여전히 직접 계산해 사용했어야 했다.)
2. 너비 우선 탐색(BFS, Breadth First Search)
너비 우선 탐색은 루트 노드(혹은 다른 임의의 노드)에서 시작해서 인접한 노드를 먼저 탐색하는 방법이다.
- 시작 정점으로부터 가까운 정점을 먼저 방문하고 멀리 떨어져 있는 정점을 나중에 방문하는 순회 방법이다.
- 즉, 깊게(deep) 탐색하기 전에 넓게(wide) 탐색하는 것이다.
- 사용하는 경우 : 두 노드 사이의 최단 경로 혹은 임의의 경로를 찾고 싶을 때 이 방법을 선택한다.
- 깊이 우선 탐색(DFS)의 경우 - 모든 노드를 탐색해야 해를 구할지도 모른다.
- 너비 우선 탐색(BFS)의 경우 - 시작 노드와 가까운 노드들부터 확인하기 때문에 보다 빠르게 해를 구할지도 모른다.
- 너비 우선 탐색(BFS)이 깊이 우선 탐색(DFS)보다 좀 더 복잡하다.
너비 우선 탐색(BFS)의 특징
- 직관적이지 않은 편이다.
- BFS는 시작 노드에서 시작해서 거리에 따라 단계별로 탐색한다고 볼 수 있다.
- BFS는 재귀적으로 동작하지 않는다.
- BFS 알고리즘을 구현할 때 가장 큰 차이점은, 그래프 탐색의 경우 어떤 노드를 방문했었는지 여부를 반드시 검사해야 한다는 것이다.
- BFS는 방문한 노드들을 차례로 저장한 후 꺼낼 수 있는 자료구조인 큐(Queue)를 사용한다.
- 큐(Queue)는 선입선출(FIFO) 원칙을 사용하기 때문에 대표적으로 사용된다.
- 즉, 선입선출을 하는 방식을 이용해 구현해야 한다.
- 일반적으로 큐(Queue)를 이용해서 반복적 형태로 구현하는 것이 가장 잘 동작한다고 한다.
- 'Prim', 'Dijkstra' 알고리즘과 유사하다.
- 깊이 우선 탐색(DFS)와 가장 큰 차이는 여러 갈래 중 무한한 길이를 가지는 경로가 존재하고, 목표 노드가 다른 경로에 존재하는 경우 DFS는 무한한 길이의 경로에서 영원히 종료하지 못하는 한편, BFS는 같은 레벨의 모든 노드를 확인해 가며 진행하기 때문에 탐색이 가능하다는 차이가 있다.
- 서론에서 특정 조건에서 최단 거리를 구할 수 있는 알고리즘이라고 했는데, 이 이유는 가중치가 없는 그래프(즉, 모든 경로의 거리(값)가 동일하다면)에서 BFS는 모든 길(경로)를 한 번씩 탐색하기 때문에 최단 경로를 구할 수 있다.
너비 우선 탐색(BFS)의 시간 복잡도
- 인접 리스트로 표현된 그래프 : O(N+E)
- 인접 행렬로 표현된 그래프 : O(N^2)
- 깊이 우선 탐색(DFS)과 마찬가지로 그래프 내에 적은 숫자의 간선만을 가지는 희소 그래프(Sparse Graph)의 경우 인접 행렬보다 인접 리스트를 사용하는 것이 유리하다.
너비 우선 탐색(BFS)의 과정
1. 시작 노드(루트 노드)에 방문하고, 방문처리 한다.
◈ 큐(Queue)에 방문된 노드를 삽입한다.
◈ 초기 상태의 큐(Queue)에는 시작 노드만이 저장된다.
2. 큐(Queue)에서 꺼낸 노드와 인접한 노드들을 모두 차례대로 방문한다.
◈ 큐(Queue)에서 꺼낸 노드를 방문한다.
◈ 큐(Queue)에서 꺼낸 노드와 인접한 노드들을 모두 방문한다.
◈ 만약 이때, 큐(Queue)에서 꺼낸 노드와 인접한 노드가 없을 경우 큐(Queue)의 앞에서 노드를 꺼낸다.
◈ 큐(Queue)에 방문된 노드를 삽입한다.
3. 큐가 소진될 때까지 반복한다.
DFS와 비교를 해보기 위해 DFS글에서 사용했던 Tree와 그래프로 살펴보자.
이렇게 각 노드가 연결된 이진트리가 있다고 가정을 하고, BFS의 순회 순서와 동작 방법을 살펴보자.
우리는 시작 노드를 Root Node인 A로 설정하고, 목표하는 노드는 K노드로 가정해 보자.
- 시작 노드에 방문해 목표 노드 인지 확인한 후, 방문처리를 한 뒤 Queue에 넣는다.
- Queue에서 가장 앞 노드를 꺼낸 뒤, 인접 노드를 확인한다. (Queue에서 가장 앞인 A를 pop()해 제거해준다.)
- 이때, 우리는 왼쪽부터 인접 노드를 확인한다고 가정해 보자.
- Queue에서 꺼냈던 A노드의 인접 노드인 B를 확인하고 방문처리를 한 뒤 Queue에 넣는다.
- A 노드의 또 다른 인접 노드인 C를 확인하고 방문처리를 한 뒤 Queue에 넣는다.
- Queu에서 가장 앞 노드인 B를 꺼낸다. (Queue에서 가장 앞인 B를 pop()해 제거해 준다.)
- B의 인접 노드인 D와 E를 차례대로 확인한 후, 방문 처리해 Queue에 넣어준다.
- Queue의 가장 앞 노드인 C를 꺼낸다. (Queue에서 가장 앞인 C를 pop()해 제거해 준다.)
- C의 인접 노드인 F와 G를 차례대로 확인한 후, 방문 처리해 Queue에 넣어준다.
- Queue의 가장 앞 노드인 D를 꺼낸다. (Queue에서 가장 앞인 D를 pop()해 제거해 준다.)
- D의 인접 노드인 H를 확인한 후, 방문 처리해 Queue에 넣어준다.
- Queue의 가장 앞 노드인 E를 꺼낸다. (Queue에서 가장 앞인 E를 pop()해 제거해 준다.)
- E의 인접 노드인 I와 J를 차례대로 확인한 후, 방문 처리해 Queue에 넣어준다.
- Queue의 가장 앞 노드인 F를 꺼낸다. (Queue에서 가장 앞인 F를 pop()해 제거해 준다.)
- F노드는 인접 노드가 없기 때문에 아무 일도 하지 않는다.
- Queue의 가장 앞 노드인 G를 꺼낸다. (Queue에서 가장 앞인 G를 pop()해 제거해 준다.)
- G의 인접 노드인 K를 확인한다. 이때, 우리가 목표한 노드에 도달했기 때문에 알고리즘을 종료해 준다.
이를 그림으로 살펴보면 다음과 같다.
방문한 순서로 따지면 다음과 같다.
즉, A - B - C - D - E - F - G - H - I -J - K 순서로 방문했었다.
BFS로 최단 경로를 구할 수 있다고 했는데, 그러면 어떻게 구해야 할까?
방문 순서로 보나, 스택에서 꺼낸 노드로 보나 최단 경로와 일치하지 않는다.
우선 예시로든 트리가 이진트리이고, 가중치가 없기 때문에 해당 노드까지 도달할 수 있는 최단 거리 값은 각 노드의 Level과 같다. 때문에 노드에 방문할 때, 이전 노드의 거리값(Cost)에 1을 더한 수를 노드에 저장해 두면, 탐색을 마치고, 목표 노드로 접근해 해당 Cost를 확인해 보면 최단 거리값이 들어있다.
만약, 경로를 찾을 경우에는 목표노드의 부모로 타고 올라가다 보면 최단 경로를 구할 수 있다.
그래프의 경우 코스트를 기록하는 방법이 유효하게 잘 동작하고, 최단 경로의 경우에도 유효하다. (구현한 방법에 따라 유효하지 않는 예외 상황도 있을 것 같은데, 아직 모르겠다.)
너비 우선 탐색(BFS) 구현 코드
이전에 프로그래머스 문제를 풀다가 BFS를 구현해 풀었던 문제가 있다. 해당 코드를 살펴보면 BFS를 구현과 최단 경로의 거리를 구하는 방법이 있다.
https://rozentea.tistory.com/43 (프로그래머스 Lv1 키패드 누르기 문제 풀이)
#include <string>
#include <vector>
#include <queue>
#define None -1
using namespace std;
struct tNode
{
int LeftNum;
int RightNum;
int UpNum;
int DownNum;
int Dist;
bool bvisit;
tNode(int Lf, int Rt, int Up, int Dn)
{
LeftNum = Lf;
RightNum = Rt;
UpNum = Up;
DownNum = Dn;
Dist = 0;
bvisit = false;
}
};
void Clear(vector<tNode>& _vecPad)
{
for (size_t i = 0; i < _vecPad.size(); ++i)
{
_vecPad[i].bvisit = false;
_vecPad[i].Dist = 0;
}
}
int calcul(vector<tNode>& _vecPad, int _StartNum, int _TargetNum)
{
queue<int> q;
q.push(_StartNum);
_vecPad[_StartNum].bvisit = true;
while (!q.empty())
{
int x = q.front();
q.pop();
if (x == _TargetNum)
{
return _vecPad[x].Dist;
}
int iLeft = _vecPad[x].LeftNum;
int iRight = _vecPad[x].RightNum;
int iUp = _vecPad[x].UpNum;
int iDown = _vecPad[x].DownNum;
if (_TargetNum == iLeft
|| _TargetNum == iRight
|| _TargetNum == iUp
|| _TargetNum == iDown)
{
return _vecPad[x].Dist + 1;
}
if (iLeft != None && !(_vecPad[iLeft].bvisit))
{
q.push(iLeft);
_vecPad[iLeft].Dist = _vecPad[x].Dist + 1;
}
if (iRight != None && !(_vecPad[iRight].bvisit))
{
q.push(iRight);
_vecPad[iRight].Dist = _vecPad[x].Dist + 1;
}
if (iUp != None && !(_vecPad[iUp].bvisit))
{
q.push(iUp);
_vecPad[iUp].Dist = _vecPad[x].Dist + 1;
}
if (iDown != None && !(_vecPad[iDown].bvisit))
{
q.push(iDown);
_vecPad[iDown].Dist = _vecPad[x].Dist + 1;
}
}
}
string solution(vector<int> numbers, string hand) {
string answer = "";
vector<tNode> vec_Pad;
// 패드 만들기
vec_Pad.push_back(tNode(10, 11, 8, None)); // 0번 숫자
vec_Pad.push_back(tNode(None, 2, None, 4)); // 1
vec_Pad.push_back(tNode(1, 3, None, 5)); // 2
vec_Pad.push_back(tNode(2, None, None, 6)); // 3
vec_Pad.push_back(tNode(None, 5, 1, 7)); // 4
vec_Pad.push_back(tNode(4, 6, 2, 8)); // 5
vec_Pad.push_back(tNode(5, None, 3, 9)); // 6
vec_Pad.push_back(tNode(None, 8, 4, 10)); // 7
vec_Pad.push_back(tNode(7, 9, 5, 0)); // 8
vec_Pad.push_back(tNode(8, None, 6, 11)); // 9
vec_Pad.push_back(tNode(None, 0, 7, None)); // 10 *
vec_Pad.push_back(tNode(0, None, 9, None)); // 11 #
int curLeftPos = 10;
int curRightPos = 11;
for (size_t i = 0; i < numbers.size(); ++i)
{
int iTargetNum = numbers[i];
if (iTargetNum == 1
|| iTargetNum == 4
|| iTargetNum == 7)
{
answer += "L";
curLeftPos = iTargetNum;
}
else if (iTargetNum == 3
|| iTargetNum == 6
|| iTargetNum == 9)
{
answer += "R";
curRightPos = iTargetNum;
}
else
{
Clear(vec_Pad);
int LeftHandDist = calcul(vec_Pad, curLeftPos, iTargetNum);
Clear(vec_Pad);
int RightHandDist = calcul(vec_Pad, curRightPos, iTargetNum);
if (LeftHandDist < RightHandDist)
{
answer += "L";
curLeftPos = iTargetNum;
}
else if (LeftHandDist == RightHandDist)
{
if (hand == "left")
{
answer += "L";
curLeftPos = iTargetNum;
}
else if (hand == "right")
{
answer += "R";
curRightPos = iTargetNum;
}
}
else
{
answer += "R";
curRightPos = iTargetNum;
}
}
}
return answer;
}전체 코드를 모두 확인할 필요 없이 BFS에 해당되는 calcul() 함수와 만든 그래프(vec_Pad)를 확인해 보면 된다.
이 외에도 프로그래머스 레벨 2 미로 탈출 문제도 괜찮은 문제 같다.
프로그래머스 2023.09.03 (2Lv 미로 탈출)
프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 문제 문
rozentea.tistory.com
함께 보면 좋은 Post
https://rozentea.tistory.com/34
https://rozentea.tistory.com/70
참고 블로그 및 자료
[알고리즘] 너비 우선 탐색(BFS)이란 - Heee's Development Blog
Step by step goes a long way.
gmlwjd9405.github.io
[Python] BFS 알고리즘 개념 및 실습
본 포스팅에서는 너비 우선 탐색이라고 불리는 BFS(Breadth-First Search)에 대해 알아봅니다. 📚 목차 1. BFS 알고리즘이란? 2. BFS 알고리즘 동작 과정 3. BFS 파이썬 구현 3.1. 소스코드 설명 3.2. 전체 소스
heytech.tistory.com