Intro
자주, 유용하게 쓰이는 알고리즘들이다. 그래프 탐색에서도 많이 쓰이지만 완전탐색 문제를 해결하는 데 쓰이기도 한다.
학부시절에는 이런 녀석들을 적당히 구현해보는 데 그쳤고, 그래프 탐색 문제에 활용하는 게 전부였다. 그래프 탐색 또한 이러한 알고리즘이 주로 쓰이는 주제기도 하지만, 완전탐색 문제에 쓰이기도 한다. 말 그대로 탐색이기 때문에 여러 분야에 활용 될 수 있다.
https://www.acmicpc.net/problem/13913 (BOJ - 숨바꼭질 시리즈)
위와 같은 문제 해결에도 BFS가 쓰인다. 무작정 Brute Force로 풀기엔 경우의 수도 많고 시간도 오래 걸린다. BFS를 활용한다면, 짧은 시간 내에 최소한의 비용이 드는 경우를 빠르게 도출해낼 수 있다.
https://www.acmicpc.net/problem/1260
DFS와 BFS라 불리는 유명한 문제다. 이 문제를 함께 보며 DFS, BFS에 대해 알아보도록 하자. 코드는 아래와 같다.
#include <iostream>
#include <queue>
#include <cstring>
#define MAX 1001
using namespace std;
int N, M, V;
int matrix[MAX][MAX];
bool visited[MAX];
queue<int> q;
void DFS(int a) {
cout << a << " ";
for (int i = 1; i <= N; i++) {
if (matrix[a][i] && !visited[i]) {
visited[i] = 1;
DFS(i);
}
}
}
void BFS(int a) {
q.push(a);
visited[a] = 1;
while (!q.empty()) {
a = q.front();
q.pop();
cout << a << " ";
for (int i = 1; i <= N; i++) {
if (matrix[a][i] && !visited[i]) {
visited[i] = 1;
q.push(i);
}
}
}
}
int main() {
cin >> N >> M >> V;
for (int i = 0; i < M; i++) {
int A, B;
cin >> A >> B;
matrix[A][B] = 1;
matrix[B][A] = 1;
}
visited[V] = 1;
DFS(V);
cout << '\n';
memset(visited, false, sizeof(visited));
BFS(V);
}
DFS
깊이 우선 탐색이다. 학부시절 알고리즘 시간에 BFS와 함께 반드시 나오는 중요한 알고리즘.
말 그대로 깊이 우선 탐색이다. 특정 노드와 연결 되어있는 노드들을 하나씩 타고 가며 더이상 탐색 할 수 없는 곳 까지 탐색하며 돌아오는 방식이다.
for (int i = 0; i < M; i++) {
int A, B;
cin >> A >> B;
matrix[A][B] = 1;
matrix[B][A] = 1;
}main에서 보다시피 데이터들은 인접 행렬 형태로 입력된다. A와 B노드가 서로 연결되어있다면 A행 B열의 값과 B행 A열의 값이 1로 마킹되는 것이다. matrix 2차원배열은 전역변수로 처리되었기 때문에 초기 값들은 모두 0이다.
int N, M, V;
int matrix[MAX][MAX];
bool visited[MAX];
queue<int> q;
void DFS(int a) {
cout << a << " ";
for (int i = 1; i <= N; i++) {
if (matrix[a][i] && !visited[i]) {
visited[i] = 1;
DFS(i);
}
}
}DFS코드를 살펴보면, for문을 통해 기준이 되는 노드를 행으로 인접행렬의 데이터들을 살펴보고 있다. 1부터 N까지 만약 A와 연결되어있는 노드가 있고 그 노드를 방문하지 않았다면 그 노드를 방문한 후, 그 노드 값을 인수로 삼아 DFS를 반복한다. 방향이라 할 게 딱히 없는게 특징이다. 인접 행렬 상에서 앞 쪽 인덱스 값들이 우선순위가 높기야 하겠지만 그러한 방향을 의도해서 코딩 한 게 아니라는 것은 쉽게 알 수 있을 것이다.
visited 행렬은 말 그대로 그 노드를 방문하였는 지 체크하는 행렬이다. 방문했던 곳을 두번 탐색하는 일을 막기 위해서다. 언젠가는 그래프 상에 노드들을 모두 탐색 할 것인데 프로그램이 계속해서 돌아가서는 안되니까.
DFS의 대표적인 특징은 다음과 같다.
- 현 경로상의 노드를 기억하기 때문에 적은 메모리를 사용한다.
- 만약 A, B, C, D 노드가 연결되어있다면 그 연결되어있는 경로 상에서만 탐색을 진행한다.
- 찾으려는 노드가 깊은 단계에 있는 경우 BFS 보다 빠르게 찾을 수 있다.
- DFS를 통해서 얻어진 해가 최단 경로라는 보장이 없다. DFS는 해에 도착하면 탐색을 종료하기 때문이다.
BFS
너비 우선 탐색이다. DFS는 노드에 연결 된 노드들을 하나 하나 타고 탐색하는 느낌이라면 BFS는 연결 되어있는 노드들을 전부 다 검색하는 느낌이다.
int N, M, V;
int matrix[MAX][MAX];
bool visited[MAX];
queue<int> q;
void BFS(int a) {
q.push(a);
visited[a] = 1;
while (!q.empty()) {
a = q.front();
q.pop();
cout << a << " ";
for (int i = 1; i <= N; i++) {
if (matrix[a][i] && !visited[i]) {
visited[i] = 1;
q.push(i);
}
}
}
}BFS는 Queue를 사용한다. 탐색을 시작하는 기준이 되는 노드 부터 Queue에 삽입하고 해당 노드를 방문 처리 한다. 그 다음 Queue에 있는 노드를 하나 pop 한 후 그 노드 기준으로 연결되어있는 노드들을 하나하나 모두 탐색한 다음, 방문 처리 후 탐색을 마친 노드들을 모두 Queue에 저장한다. DFS와는 다르게 한 노드를 쭉 타고 가는 느낌이 아니라 연결되어있는 모든 노드들에 대한 정보들을 저장 후, 순서대로 똑같이 탐색을 진행한다. 메모리는 확실히 BFS가 더 많이 차지하겠지만 BFS의 다음과 같은 특징 때문에 체감상으로는 BFS를 더 자주 쓰는 것 같다.
- 최단 경로를 찾을 수 있다.
- DFS와는 다르게 연결되어있는 모든 노드들을 공평하게 체크한다. 미로 찾기로 비유를 하자면 DFS는 한 방향을 끝까지 가 보고 돌아온 다음 다른 방향으로 가는 느낌이라면, BFS는 모든 방향으로 한 걸음 씩 탐색 해 보는 느낌이다. 즉 제일 먼저 목적지에 도착하는 경우는 최단 경로라고 할 수 있다.
- 경로가 매우 길 경우에는 탐색 가지가 급격히 증가함에 따라 보다 많은 기억 공간 필요하다.
- DFS와는 다르게 Queue를 따로 두어서 경우들을 저장한다. 노드가 많으면 많을수록 Queue안에 들어가는 데이터 또한 많아진다. 물론 DFS 또한 재귀함수로 구현한다면 Stack 영역에 많은 메모리를 차지할 수도 있겠지만, 한 경로에 대해 탐색이 끝나는대로 Return 된다. 그렇지만 BFS는 모든 탐색이 끝날 때 까지는 Queue를 사용하게 된다.
Outro
지금까지 BFS와 DFS의 특징들을 알아보았다. 혼자 공부를 하다보니 이러한 정리노트가 필요하다고 생각해서 글을 쓰기 시작했다. 이왕 공부하는 거 지식을 공유해볼 겸, 글쓰기 실력을 올려볼 겸...좋은 결과가 있지 않을까?
