너비 우선 탐색(Breadth-First Search) 알고리즘은 깊이 우선 탐색(Depth-First Search) 알고리즘과 마찬가지로 완전 탐색(맹목적 탐색)의 일종입니다. 하지만 특정 루트의 최대한 깊은 루트를 탐색하는 DFS와 다르게 BFS는 특정 노드의 인접한 노드들부터 탐색합니다. 주로 큐 자료구조를 사용해서 인접노드들을 차례로 탐색하게 됩니다. 보통 '가중치가 없거나 일정한 간선을 가진 노드들의 최단 경로'를 구할 때 사용하는 알고리즘입니다.
개요
DFS(깊이우선탐색) 알고리즘 포스팅과 마찬가지로 본 포스팅에서는 BFS(너비우선탐색)의 개념과 이론 설명은 생략하도록 하겠습니다. 개념 및 이론 이해가 필요한 분들께서는 서적과 다른 인터넷 사이트를 참고해주시면 감사하겠습니다.
본 포스팅에서는 BFS 알고리즘을 빠르게 구현하는 꿀팁 아닌 꿀팁(?)에 대해서 작성하도록 하겠습니다.
꿀팁 같은 꿀팁 아닌 꿀팁인 이유 (DFS 포스팅과 동일)
- 야매(?), 가라(?) 들과 같은 꿀팁은 아닙니다. 정석적인 BFS 알고리즘의 구현입니다.
- 알고리즘 구현에 익숙하시고 능수능란한 분들께는 당연한 내용일 수 있습니다.
- 본 포스팅이 100% 도움된다고 확신할 수 없습니다.
- BFS 알고리즘을 구현할 때, 구현 코드가 기억이 잘 안나거나 이미지가 잘 떠오르지 않는 분들께 강추드리는 방법입니다.
- 4번과 같은 경험을 가진 분들이 본 포스팅의 내용일 익힌다면 BFS 알고리즘 구현에 많은 시간 단축이 가능할 것입니다.
- 본 포스팅에서 설명하는 내용은 "삼성 SDS 대학생 알고리즘 특강"의 강사님께서 가르쳐주신 내용이며 문제가 될시 삭제하겠습니다. 해당 강사님께 감사의 말씀을 전하며 많은 초보 개발자분들에게 작은 도움이 될 수 있을까해서 본 포스팅을 작성하게 되었습니다.
본문
본 몬문에서 BFS 알고리즘 구현을 익히는 과정을 번호 순서대로 작성하도록 하겠습니다.
1. 6단계의 구현 과정을 암기합니다.
BFS 알고리즘 역시 DFS 알고리즘 구현 단계와 마찬가지로 6단계로 구성됩니다. 먼저 아래 6단계를 반복해서 암기하여야 합니다. (더보기를 통해 암기에 활용해보세요!)
1. 큐에서 꺼낸다
2. 목적지인가
3. 연결된 곳 순회
4. 갈 수 있는가
5. 체크인
6. 큐에 넣는다DFS 알고리즘 구현 과정과 거의 유사한 형태입니다. DFS 알고리즘의 6단계 구현을 암기하면 BFS 알고리즘 구현 과정도 어렵지 않게 암기가 가능할 것입니다. 각 단계가 어떤 것을 의미하는지는 아래 구현 과정에서 설명하도록 하겠습니다.
2. 구현할 위치에 6단계를 주석으로 적어놓습니다.
BFS 알고리즘 함수를 구현할 위치에 1번 과정에서 암기한 6단계를 주석으로 적어놓습니다. BFS 알고리즘은 큐를 선언한 이후에 while 반복문 내에서 구현됩니다. 주석을 먼저 적어놓으면 많은 생각없이 신속하게 코드를 작성할 수 있기 때문에 먼저 주석을 작성하는 습관을 가져야 합니다.
void bfs(int start){
queue<int> q;
q.push(start);
visit[start] = true;
while(!q.empty()){
// 큐에서 꺼낸다
// 목적지인가
// 연결된 곳 순회
// 갈 수 있는가
// 체크인
// 큐에 넣는다
}
}위와 같은 순서대로 먼저 주석을 작성해 놓으면, 어떠한 완전 너비 우선 탐색 문제를 해결하더라도 약간의 응용만 있을뿐 거의 위와 같은 순서로 해결할 수 있습니다. (5번 '체크인'은 DFS와 다르게 반드시 큐에 넣기 전에 위치하여야 합니다. 그래야 다른 노드에서 큐에 중복으로 넣는 것을 방지할 수 있습니다.)
첫번째 시작점에 대한 처리는 while 반복문 이전에, 큐에 삽입하고 체크인 처리 코드를 작성해줍니다.
3. 주석의 내용대로 구현 코드를 작성합니다. (C++ 로 작성)
너비 우선 탐색을 적용할 수 있는 문제는 그래프에서의 최소 이동 횟수(가중치 없는 최단경로), 서로 다른 탐색, 이분 그래프 탐색 문제 등에서 활용할 수 있겠습니다. C++ 코드 구현을 통해 예시를 보겠습니다.
예시1 (최소 이동 횟수, 가중치 없는 최단 경로)
이차원 그래프로 주어진 미로 (0,0)에서 (N-1, M-1)까지 최소 이동 횟수로 탈출하는 값을 구하는 알고리즘입니다.
int maze[MAX][MAX];
bool visit[MAX][MAX];
int cnt[MAX][MAX];
int dy = {-1, 0, 1, 0};
int dx = {0, 1, 0, -1};
int bfs(){
queue<pair<int, int>> q;
q.push(make_pair(0, 0));
visit[0][0] = true;
cnt[0][0] = 1;
int ret = 0;
while(!q.empty()){
// 큐에서 꺼낸다
pair<int, int> cur = q.front();
q.pop();
// 목적지인가
if(cur.first == N-1 && cur.second == M-1){
ret = cnt[N-1][M-1];
break;
}
// 연결된 곳 순회
for(int i=0; i<4; i++){
int ty = cur.first + dy[i];
int tx = cur.second + dx[i];
// 갈 수 있는가
if(0<=ty && ty<N && 0<=tx && tx<M && maze[ty][tx] == 1 && !visit[ty][tx]){
// 체크인
visit[ty][tx] = true;
cnt[ty][tx] = cnt[cur.first][cur.second] + 1;
// 큐에 넣는다
q.push(make_pair(ty, tx));
}
}
}
return ret;
}- 큐에서 꺼낸다 과정에서 큐에 존재하는 탐색할 노드를 꺼냅니다. 이때, 언어마다 pop 또는 poll 하는 과정에서 값을 반환하는 경우가 있을 수도 없을 수도 있으니 언어별로 쓰임에 유의해야 합니다.
- 목적지인가 확인하는 과정은 문제와 조건에 따라 많이 다를 수 있습니다. 위 예시에서는 미로의 (N-1, M-1)에 도달한 경우에 탐색을 종료하는 문제였기 때문에 (N-1, M-1)인 경우 종료하는 조건의 코드를 작성했습니다. 종료 조건이 없을 수도 있으나 종료 조건에 도달하면 while 반복문을 종료시키면 되겠습니다.
- 연결된 곳 순회하는 과정은 역시 문제에 따라 다릅니다. 위 예시처럼 이차원 그래프 탐색의 경우에 y축, x축의 이동방향으로 순회하면 되겠습니다.
- 갈 수 있는가 확인하는 과정은 범위에서 벗어나는지, 갈 수 있는 곳인지, 방문한 곳인지 등을 체크하면 되겠습니다. 위 예시 문제의 경우 미로에서 1의 값만 이동할 수 있으므로 1인지 확인하는 조건을 추가하였습니다.
- 체크인 과정에서는 갈 수 있는지 확인이 되면 방문체크와 그 외 카운트라든지 등을 처리해주는 과정입니다. DFS 깊이 우선 탐색과 다르게 체크인 과정은 이 과정에서만 해야합니다. 이유는 노드를 이동하기 전에 갈 수 있는 모든 노드를 큐에 넣게 되는데 만약 다른 노드에서 큐에 넣게 된다면 중복 탐색이 발생하게 됩니다. 예를 들어 [1, 2] 가 큐에 들어가 있는 상태에서 1에서 3으로 갈 수 있으면 [1, 2, 3] 에 큐로 저장됩니다. 그런데 만약 2에서도 3을 갈 수 있게되면 방문체크를 안한 경우에 [1, 2, 3, 3] 이라는 큐가 저장되어 중복 탐색이 이뤄지게 됩니다.
위 예시에서는 카운트 배열 자료구조를 만들어 현재 노드에서 다음 노드로 넘어갈 때 카운트 값을 더해주는 방식으로 이동 횟수를 체크하였습니다. - 큐에 넣는다 과정에서는 작업 큐에 넣어서 마무리하는 과정입니다. 큐의 자료구조에 따라 삽입하면 되겠습니다. 위 예시에서는 pair 자료 구조로 행과 열을 저장하였습니다. 때로는 구조체나 클래스를 만들어서 저장하는 경우도 있겠습니다.
예시2 (1차원 배열 이동)
1차원 배열 상에서 여러 이동 방법이 주어졌을 때 이동하며 최소 시간 값을 구하는 알고리즘입니다.
int time[MAX+1];
int d[2] = {-1, 1};
void bfs(int a){
queue<int> q;
q.push(a);
time[a] = 0;
while(!q.empty()){
// 큐에서 꺼내다
int cur = q.front();
q.pop();
// 연결된 곳 순회
for(int i=0; i<3; i++){
if(i==2){
int tx = cur * 2;
// 갈 수 있는가
if(0<= tx && tx<=MAX && time[tx]>time[cur]){
// 체크인
time[tx] = time[cur];
// 큐에 넣는다
q.push(tx);
}
} else {
int tx = cur + d[i];
// 갈 수 있는가
if(0<= tx && tx<=MAX && time[tx]>time[cur]+1){
// 체크인
time[tx] = time[cur]+1;
// 큐에 넣는다
q.push(tx);
}
}
}
}
}- 큐에서 꺼낸다 과정에서 역시 현재 노드 위치를 저장합니다.
- 목적지인가 확인하는 과정은 위 예시에서는 생략되었습니다. 이처럼 목적지가 없는 경우에는 큐가 비워질때까지 모든 곳을 탐색하는 완전탐색이겠습니다.
- 연결된 곳 순회하는 과정에서 여기서는 d배열을 보면 -1, 1로 가는 방법과 *2 로 가는 방법이 있습니다. 이처럼 여러 이동 방법이 주어졌을 때 그 방법을 모두 순회하며 갈 수 있는 경우 큐에 넣으면 되겠습니다.
- 갈 수 있는가 확인하는 과정에서 역시 범위 확인과 time 이라는 동적 프로그래밍을 사용한 배열과 비교하여 작을경우 값을 갱신해주는 경우입니다.
- 체크인 과정에서 위 예시는 time 배열을 갱신하는 식으로 해주었습니다.
- 큐에 넣는다 과정에서는 역시 갈 수 있는 노드를 작업 큐에 넣어서 마무리합니다.
예시3 (인접 리스트 탐색 & 이분 그래프)
아래 예시는 인접한 노드끼리는 같은 집합에 속하지 않도록 하는 그래프(이분 그래프)를 찾는 알고리즘입니다. 인접 리스트로 자료구조를 저장하였으며 인접한 노드를 서로 다른 색으로 칠하는 방식으로 구현합니다. 저는 flag라는 배열로 서로 다른 집합을 표현하였습니다.
void bfs(int start){
queue<int> q;
q.push(start);
flag[start] = 1;
while(!q.empty()){
// 큐에서 꺼낸다
int cur = q.front();
q.pop();
// 연결된 곳 순회
for(int i=0; i<adj[cur].size(); i++){
int t = adj[cur][i];
// 갈 수 있는가
if(flag[t] == 0){
// 체크인
if(flag[cur]==1) flag[t] = 2;
else flag[t] = 1;
// 큐에 넣는다
q.push(t);
} else if(flag[cur] == flag[t]){
ans = false;
return;
}
}
}
}- 큐에서 꺼낸다 과정에서 현재 노드 위치를 저장합니다.
- 목적지인가 확인하는 과정은 위 예시에서도 생략되었습니다.
- 연결된 곳 순회하는 과정에서 인접한 노드들을 탐색합니다.
- 갈 수 있는가 확인하는 과정에서는 색(flag)이 정해지지 않은 경우에는 현재 노드의 색을 확인하여 인접한 노드들의 색을 정해줍니다. 위 예시에서는 현재 노드가 1일 경우 인접노드를 2로 저장하고 그 반대의 경우 1로 저장합니다.
만약 인접노드의 색이 같을 경우 이분 그래프가 아니므로 false로 처리하고 종료합니다. - 체크인 과정에서 색을 저장합니다.
- 큐에 넣는다 과정에서는 갈 수 있는 인접노드를 작업 큐에 저장 후 마무리합니다.
정리
이번 포스팅의 너비 우선 탐색 알고리즘을 통해 완전 탐색 알고리즘의 한 가지 구현방법을 정리하였습니다. 깊이 우선 탐색과 너비 우선 탐색의 차이점을 확실히 익혀 어느 문제에서 완전 탐색으로 활용해야하는지를 잘 파악하면 좋을 것 같습니다.
결론
본 포스팅에서는 BFS 알고리즘을 작성할 때, 많은 생각없이 효율적으로 빠르게 구현할 수 있도록 도움을 드리고자 작성하였습니다. 아래 DFS 포스팅을 확인하여 BFS 와의 구현 차이점을 확인하면 익히는데 더 많은 도움이 되겠습니다.
DFS 알고리즘의 경우 백트래킹, 단절선/단절점 찾기, 사이클 찾기 등 BFS 알고리즘의 경우 가중치 없는 최단경로, 위상정렬 등 다양한 알고리즘에 활용할 수 있으니 기본적으로 신속하게 작성하는 방식을 익히두면 좋을 것 같습니다.
다양한 완전 탐색 알고리즘 문제를 해결해보면서 보완하거나 추가해야할 사항이 생기면 수정하겠습니다. 추가 의견이나 피드백 주시면 감사하겠습니다.
깊이 우선 탐색(DFS, Depth-First Search) 알고리즘 포스팅은 다음 링크에서 확인할 수 있습니다.
https://devluce.tistory.com/16
[알고리즘] 깊이 우선 탐색(DFS, Depth-First Search) 구현 꿀팁 아닌 꿀팁(?)
깊이 우선 탐색(Depth-First Search) 알고리즘은 완전 탐색(맹목적 탐색)의 일종으로 특정 루트에서 최대한 깊은 루트까지 탐색하고 다시 돌아와 다른 루트를 탐색하는 방식의 알고리즘입니다. 주로
devluce.tistory.com
'Note > PS (Algorithm)' 카테고리의 다른 글
| [알고리즘] 최단 경로 알고리즘 비교 및 사용 케이스 정리 (0) | 2021.10.18 |
|---|---|
| [알고리즘] PS 및 알고리즘 코드 작성 언어별 비교 (0) | 2021.10.05 |
| [알고리즘] 깊이 우선 탐색(DFS, Depth-First Search) 구현 꿀팁 아닌 꿀팁(?) (0) | 2021.09.06 |
| [알고리즘] 최소 신장 트리(Minimum Spanning Tree / MST) 개요 및 개념 (0) | 2021.08.29 |
| [알고리즘] 유니온-파인드(Union-Find) & 서로소 집합(Disjoint Set) 개요 및 개념 (0) | 2021.08.24 |
