[알고리즘] 깊이 우선 탐색(DFS)과 너비 우선 탐색(BFS)

🔻그래프 탐색 알고리즘

 이번에는 그래프를 탐색하는 알고리즘에 대하여 다루어 볼 것이다. 그래프 탐색 알고리즘이란 한 정점에서 시작하여 차례대로 그래프에 있는 모든 정점들은 한번씩 방문하는 알고리즘을 뜻한다. 많은 그래프에 대한 문제를 해결하기 위해서 그래프 탐색 알고리즘을 알아야하는데 예를들어 다음과 같은 상황에서 탐색이 필요하다.

• 한 정점과 다른 정점의 경로를 구할 때
• 그래프가 연결되어 있는지 확인할 때
• 신장 트리(Spanning Tree)를 찾을 때

 그래프를 탐색하는 알고리즘은 굉장히 중요한 알고리즘이라고 들었다. 알고리즘 사이트인 프로그래머스에서 보았을 때도 그래프 탐색이 출제 빈도수도 높고 정답률이 낮게 나온다.

 대표적으로 깊이 우선 탐색(Depth-First Search)과 너비 우선 탐색(Breadth-First Search)이 존재한다. 줄여서 각각 DFS와 BFS라고 많이 부른다.

 

그래프(Graph)라는 자료구조에 대한 자세한 설명은 아래의 포스팅에 잘 정리해 두었다.

그래프(Graph)

 

 

 

 

 

🔻깊이 우선 탐색(DFS)과 너비 우선 탐색(BFS)

그래프를 탐색하는 알고리즘은 깊이 우선 탐색과 너비 우선 탐색으로 나누어 진다. 두 알고리즘을 알아보자.

 

 

 

---

💡 깊이 우선 탐색(DFS - Depth-First Search)

 오른쪽 그림을 보면 이해가 쉬울 것이다. DFS의 기본 원리는 갈 수 있는 만큼 최대한 깊이가고, 더이상 갈곳이 없으면 이전 정점으로 돌아간다는 것이다. 쉽게 말해서 그냥 세로로 한줄씩 읽어 내려간다고 생각하면 된다. stack과 재귀함수를 사용하여 구현한다.

 

 

 

DFS의 장/단점

• 장점
  • 현 경로상의 노드들만 기억하면 되므로 저장공간 수요가 비교적 적다.
  • 목표 노드가 깊은 단계에 있을 경우 해를 빨리 구할 수 있다.
• 단점
  • 해가 없는 경로가 깊을 경우 탐색시간이 오래 걸릴 수 있다.
  • 얻어진 해가 최단 경로가 된다는 보장이 없다.
  • 깊이가 무한히 깊어지면 스택오버플로우가 날 위험이 있다. (깊이 제한을 두는 방법으로 해결가능)

 

DFS의 구현

그래프를 인접 행렬(adjacency matrix)로 구현했는지, 인접 리스트(adjacency list)로 구현했는 지에 따라 구현방법이 달라진다.

 

• 인접 행렬로 구현했을 경우

vector<vector<int>> adjacent; //인접 행렬로 구현된 그래프 들어감
vector<bool> visited; // 그래프의 정점만큼의 크기로 생성

void DFS(int now)
{
	visited[now] = true;
	int N = adjacent.size();
	for (int i = 0; i < N; i++)
	{
		if (adjacent[now][i] == 0)
			continue;
		
		if (!visited[i])
			DFS(i);
	}
	
}

[시간복잡도]

 DFS 하나당 N번의 loop를 돌게 되므로 O(n)의 시간복잡도를 가진다. 그런데 N개의 정점을 모두 방문 해야하므로

n*O(n)이므로 O(n^2)의 시간복잡도를 가지게 된다.

 

• 인접 리스트로 구현했을 경우

vector<vector<int>> adjacent; //인접 리스트로 구현된 그래프 들어감
vector<bool> visited; // 그래프의 정점만큼의 크기로 생성

void DFS(int now)
{
	visited[now] = true;

	for (int i = 0; i < adjacent[now].size(); i++)
	{
		int next = adjacent[now][i];
		if (!visited[next])
			DFS(next);
	}
	
}

[시간복잡도]

 DFS가 총 N번 호출되긴 하지만 인접행렬과 달리 인접 리스트로 구현하게 되면 DFS하나당 각 정점에 연결되어 있는 간선의 개수만큼 탐색을 하게 되므로 예측이 불가능 하다. 하지만 DFS가 다 끝난 후를 생각하면, 모든 정점을 한번씩 다 방문하고, 모든 간선을 한번씩 모두 검사했다고 할 수 있으므로 O(n+e)의 시간이 걸렸다고 할 수 있다.

따라서 시간복잡도는 O(n+e)이다.

 

 

 

 

 

 

 

 

 

💡 너비 우선 탐색(BFS - Breadth-First Search)

 마찬가지로 오른쪽 그림을 보면 이해가 쉬울 것이다. BFS의 기본 원리는 queue를 이용하여 지금 위치에 갈 수 있는 정점을 모두 queue에 넣는 것이다. 쉽게 말하면 DFS와는 정반대로 가로로 한줄씩 읽는다고 생각하면 된다. queue를 사용하여 구현한다.

 

 

 

BFS의 장/단점

• 장점
  • 너비를 우선으로 탐색하므로 답이 되는 경로가 여러 개인 경우에도 최단경로를 얻을 수 있다.
  • 경로가 무한히 깊어져도 최단경로를 반드시 찾을 수 잇다.
  • 노드 수가 적고 깊이가 얕은 해가 존재할 때 유리하다.
• 단점
  • DFS와 달리 큐를 이용하여 다음에 탐색할 정점들을 저장하므로 더 큰 저장공간이 필요하다.

 

BFS의 구현

그래프를 인접 행렬(adjacency matrix)로 구현했는지, 인접 리스트(adjacency list)로 구현했는 지에 따라 구현방법이 달라진다.

 

• 인접 행렬로 구현했을 경우

vector<vector<int>> adjacent; //인접 행렬로 구현된 그래프 들어감
vector<bool> discovered; // 그래프의 정점만큼의 크기로 생성

void BFS(int now)
{
	queue<int> q;
	int N = adjacent.size();
	
	q.push(now);
	discovered[now] == true;
	
	while(!q.empty())
	{
		now = q.front();
		q.pop();
		
		for (int i = 0; i < N; i++)
		{
			if (adjacent[now][i] == 0)
				continue;
			
			if (!discovered[i])
			{
				q.push(i);
				discovered[i] = true;
			}
		}
	}
}

[시간복잡도]

 정점 한개당 N번의 for loop를 돌기 때문에 O(n)의 시간이 걸리는데 이 for loop는 큐에 아무것도 없을 때까지 즉, 모든 정점을 방문할 때까지 실행되므로 n번 반복 실행된다. 따라서 시간복잡도는 O(n^2)이다.

 

• 인접 리스트로 구현했을 경우

vector<vector<int>> adjacent; //인접 리스트로 구현된 그래프 들어감
vector<bool> discovered; // 그래프의 정점만큼의 크기로 생성

void BFS(int now)
{
	queue<int> q;

	q.push(now);
	discovered[now] == true;
	
	while(!q.empty())
	{
		now = q.front();
		q.pop();
		
		for (int i = 0; i < adjacent[now].size(); i++)
		{
			int next = adjacent[now][i];
			if (!discovered[next])
			{
				q.push(next);
				discovered[next] = true;
			}
		}
	}
}

[시간복잡도]

 아까 리스트로 구현된 DFS와 비슷한 논리로 시간복잡도를 구할 수 있다.

BFS가 다 끝난 후를 생각해보면, 모든 간선에 대해서 한번씩 검사를 할 것이고, 각 정점을 한번씩 모두 방문하기 때문에 O(n+e)만큼의 시간복잡도를 가질 것이다.

 

 

 

 

 

 

🔻마치며

 이렇게 그래프를 탐색하는 알고리즘인 DFS와 BFS에 대해서 알아보았다. 두 알고리즘 모두 인접행렬을 사용하여 만든 그래프의 경우에는 O(n^2)의 시간복잡도를 가지고 인접리스트를 사용하여 만든 그래프의 경우에는 O(n+e)의 시간복잡도를 가진다. 두 알고리즘의 시간복잡도는 같으므로 각각의 장단점을 알고 상황에 따라 적절한 알고리즘을 선택하는 것이 중요해 보인다.

 DFS, BFS알고리즘은 굉장히 중요한 알고리즘이란 것을 인지하고 계속해서 반복학습 해나가야 한다고 생각한다.