컴과나, 소프트웨어 관련 학부생일 경우 2학년때부터는 항상 이름은 익히 들어봤고, 뭐 하는 애들인지는 알지만 어떻게 구현하는건지는 까먹은 DFS와 BFS.
그래프의 탐색 방법의 대표적인 두 가지 이다.
그래프 탐색의 목적은 모든 정점을 한 번씩 방문 하는 것이다. 어떻게 방문할 것이냐에 따라 DFS와 BFS로 나뉘는데, 크게 봤을 때는 다음과 같이 구분할 수 있다.
| 구분 | 동작 원리 | 구현 방법 | |
|---|---|---|---|
| DFS | 깊이 우선 탐색 | 최대한 깊이 | stack |
| BFS | 너비 우선 탐색 | 최대한 넓게 | queue |
각각의 탐색 방법에 대하여 자세히 알아보도록 하자.
DFS (Depth First Search)
DFS의 기본 작동 방식은 stack을 이용해서 갈 수 있는 만큼 최대한 깊이 가고, 더 이상 갈 곳이 없다면 이전 정점으로 돌아간다는 것이다.
stack과 recursive function을 이용하여 구현한다.
그래프를 인접 행렬로 표현할 경우
void dfs(int x)
{
check[x] = true;
for(int i = 1; i <= V ; i++)
{
if(graph[x][i] == 1 && !check[i])
dfs(i);
}
}
DFS의 시간 복잡도
DFS 하나에 for loop을 V 만큼 돌기 때문에, O(V) 시간이 필요함.
정점을 방문할 때 마다 DFS를 부르는데, V개의 정점을 모두 방문하므로
DFS의 전체 시간복잡도 = V * O(V) = O(V^2)
그래프를 인접 리스트로 표현할 경우
void dfs(vector<int> *graph, bool *check, int x)
{
check[x] = true;
for(int i = 0; i < graph[x].size(); i++)
{
int next = graph[x][i];
if(!check[next])
dfs(next);
}
}DFS의 시간 복잡도
DFS는 총 V번 부르게 된다. 그러나, 인접 행렬로 구현한 경우와 달리 인접 리스트로 구현한 DFS는 DFS 하나당 각 정점에 연결되어 있는 간선의 개수만큼 탐색을 하게 되어 DFS 하나의 수행 시간이 일정하지 않다.
전체 DFS가 다 끝난 이후를 생각해 보면, DFS가 다 끝났을 시점에는 모든 정점을 한번씩 방문하고, 모든 간선을 한번씩 검사하게 되므로 O(V+E)의 시간이 걸린다고 말할 수 있다.
따라서, 인접리스트로 구현할 경우 DFS의 시간 복잡도는 O(V+E)이다.
BFS (Breadth First Search)
BFS의 기본 작동 방식은 queue를 이용하여 지금 위치에서 갈 수 있는 것들을 모두 큐에 넣는 방식이다. 이때, queue에 넣을 시점에 해당 노드를 방문했다고 체크해야 한다. (DFS는 일단 들어가서 체크함)
BFS는 queue와 while loop을 이용하여 구현한다.
그래프를 인접 행렬로 표현한 경우
void BFS(int V, int start)
{
queue<int> q;
bool check[V+1] = {false};
check[start] = true;
q.push(start);
while(!q.empty())
{
int now = q.front();
q.pop();
for(int i = 1; i <= V; i++)
{
if(graph[now][i] == 1 && !check[i])
{
check[i] = true;
q.push(i);
}
}
}
}BFS의 시간 복잡도
시간 복잡도를 계산할 때 가장 핵심이 되는 코드는 if(graph[now][i] == 1 && !check[i]) 부분이다.
정점 하나당 for loop으로 인해 해당 코드가 실행하는데 O(V)의 시간이 걸린다. 게다가, 이 for loop은 while loop을 통해 모든 정점을 한 번씩 방문할 때마다 실행되므로 V번 반복 실행된다.
따라서, 인접 행렬로 구현할 경우 BFS의 시간 복잡도 = V * O(V) = O(V^2) 이다.
그래프를 인접 리스트로 표현한 경우
void BFS(vector<int> *graph,int V, int start)
{
queue<int> q;
bool check[V+1] = {false};
check[start] = true;
q.push(start);
while(!q.empty())
{
int now = q.front();
q.pop();
for(int i = 0; i < graph[now].size(); i++)
{
int next = graph[now][i];
if(!check[next])
{
check[next] = true;
q.push(next);
}
}
}
}BFS의 시간 복잡도
연결 리스트를 바탕으로 구현된 DFS의 시간 복잡도를 구할 때와 비슷한 논리로 시간 복잡도를 구할 수 있다.
인접 행렬을 이용할 때와 마찬가지로 시간 복잡도의 핵심이 되는 부분은 if(graph[now][i] == 1 && !check[i]) 부분인데, 이 부분이 반복 횟수가 일정하지 않은 for loop안에 들어가 있다.
BFS가 끝난 뒤를 생각해 보면, 해당 라인은 모든 간선에 대해서 한 번씩 비교할 것이기 때문에 총 E번 반복할 것이고, 각 정점을 한 번씩 모두 방문하여 V의 시간이 걸릴 것이다.
따라서, 인접 리스트로 구현한 BFS의 시간 복잡도는 O(V+E) 이다.
출처
백준 알고리즘 인강
