[알고리즘 정리] - DFS(Deprth First Search), BFS(Breadth First Search)

 

 

 

 이번에는 경로 탐색의 대표적인 알고리즘인 DFS와 BFS에 대해 정리해보려고 한다.

 

 

 

 

 

 

https://teachingforme.tistory.com/37

[자료구조] - 그래프(Graph)

 

 

 

 

 

 

 경로탐색 알고리즘은 기본적으로 그래프 자료구조를 통해 이루어지며 그래프에 대한 내용은 위의 글에서 정리하였다. 이번 글에서 정리할 DFS(Depth First Search), BFS(Breadth First Search)는 모든 edge(간선)의 가중치가 동일한(없는) 그래프에서 사용하는 최단 경로 탐색 알고리즘이다.

 

 

 

 

 

 

 

 

 

 

 

DFS

 

 

 

 

 

DFS는 Depth First Search의 약자이며 깊이우선 탐색이라 불린다. 우선 아래와같은 방향 그래프가 있다고 가정해보자.

 

 

 

 

 

방향 그래프

 

 

 

 

 

 

 출발지를 0번 vertex라 하고, 목적지 4번 vertex까지의 최단 경로를 구하고자 할때, 어떤 것이 최단 경로일까? 사람의 입장에서 눈대중으로 본다면 0->3->4의 순서대로 나아가는 것이 최단 경로라는 것은 금방 눈에 보일 것이다.

 

 

 

 

 

 

 

 

 

그렇다면 컴퓨터에서는 그것을 어떻게 찾아야 할까? 우선 0번 vertex에서 1번 vertex로 이동해보자. 1번 vertex와 연결된 vertex는 2번과 3번이다. 우선 번호가 작은 2번 vertex를 먼저 방문,  더 이상 나아갈 수 없으므로 다시 1번 vertex로 되돌아와 3번 vertex를 방문. 3번 vertex에서 4번 vertex로 나아가고 최단 경로의 거리를 3이라고 기록한다.

 

 

 

 

 

 

 

 

 

 

 그 이후 다시 0번으로 돌아온다. 아직 0번 vertex에서 3번 vertex로 방문하는 경우를 확인하지 않았으므로 3번 vertex를 방문, 3번 vertex는 4번 vertex로 연결되어 있으므로 4번을 vertex를 방문하여 목적지에 도착하고 최단 경로를 2로 갱신한다.

 

 

 

 

 

 

 

 

 

 

 이후 다시 0번으로 돌아오고 모든 인접 노드들을 방문하였으므로 탐색을 종료한다. DFS는 위와 같은 과정을 거쳐 0번 vertex에서 4번 vertex로의 최단 경로를 찾는다.

 

 

 

 

 

 

 

 위와 같은 과정은 재귀함수 혹은 스택을 사용하여 구현이 가능하다. 재귀를 통해 구현한 코드는 아래와 같다.

 

 

 

 

 

void Dfs(int here)
{
	visited[here] = true; // 방문 처리
	cout << "Visited : " << here << endl;

	// 모든 인접 정점을 순회한다
	for (int there = 0; there < 6; there++)
	{
		if (adjacent[here][there] == 0) // 연결되지 않은 경우 무시
			continue;

		if (visited[there] == false) // 아직 방문하지 않은 vertex인 경우
			Dfs(there); // 방문 시도
	}
}

 

 

 

 

 

 Dfs 함수에 시작 위치인 0을 넘겨서 실행하게 되면 0, 1, 2, 3, 4 vertex의 순으로 정점들을 방문한다. 5번 vertex의 경우 최단 경로가 존재하지 않기 때문에 방문하지 못한다.

 

 

 

 

 

 만약 4번까지의 최단 경로의 거리를 구하고자 하는 경우 Dfs 함수를 호출할 때마다 현재 이동 거리를 기록하는 방식으로 0번 vertex에서 4번 vertex까지의 최단경로의 거리를 기록할 수도 있을 것이다. 최단 경로를 구하고자 한다면 최단 경로 갱신 시 현재 이동 경로를 최단 경로에 갱신시키는 방법으로 최단 경로도 구할 수 있다.

 

 

 

 

 

 

 

 

 

 

 

 

BFS

 

 

 BFS는 Breadth First Search의 약자이며 넓이우선 탐색이라 불린다. 마찬가지로 아래의 동일한 그래프를 통해 0번 vertex에서 4번 vertex까지의 최단 경로를 탐색한다고 가정해보자.

 

 

 

 

 

방향 그래프

 

 

 

 DFS가 이동할 수 있는 곳까지 계속해서 파고들어 가는 방식이었다면 BFS는 Queue 자료구조를 이용하여 아직 방문하지 않은 vertex를 발견하는 경우 Queue에 삽입하여 다음에 방문할 vertex로 예약하는 방식으로 최단 경로를 탐색한다.

 

 

 

 

 

 

 

 

 따라서 BFS를 이용하여 0번 vertex에서 4번 vertex로의 최단 경로를 찾는 과정은 아래와 같다.

 

 

 

 

 

 우선 0번 vertex에서 인접한 1, 3번 vertex는 방문한 적이 없으므로 Queue에 담아 예약한다. 이후 먼저 삽입된 1번 vertex에 방문한 후 또다시 인접한 2, 3번 vertex에 대해 발견한 적이 있는 vertex인지 검사한다. 2번 vertex는 발견된 적이 없으므로 Queue에 삽입하고 3번 vertex는 이미 Queue에 삽입되어(발견되어) 있으므로 무시한다.

 

 

 

 

 

 

 

 

 

 1번 vertex의 방문이 끝난 후 Queue에 삽입되어 있던 3번 vertex를 방문한다. 마찬가지로 4번 vertex에 대해 발견한 적이 없으므로 Queue에 삽입한 후 방문을 종료, 다시 Queue에 삽입되어 있던 2번 vertex를 방문한다. 2번 vertex의 경우 더 이상 인접한 방문 가능 vertex가 없으므로 방문 종료.

 

 

 

 

 

 

 

 

 

 이후 Queue에 삽입된 4번 vertex를 방문, 4번 vertex에서도 더 이상 방문 가능한 vertex가 없으므로 방문 종료. 이때 Queue안에 더 이상 방문할 vertex가 없으므로 BFS를 종료한다.

 

 

 

 

 

 

 

 

 

void Bfs(int here)
{
	// 누구에 의해 발견 되었는지 기록
	vector<int> parent(6, -1);
	// 시작점에서 얼만큼 떨어져 있는지 기록
	vector<int> distance(6, -1);

	queue<int> q; // 다음에 방문할 vertex 예약용 Queue
	q.push(here);
	discovered[here] = true; // 발견한 vertex 기록

	parent[here] = here;
	distance[here] = 0;

	while (q.empty() == false)
	{
		here = q.front();
		q.pop();

		cout << "Visited : " << here << endl;

		for (int there = 0; there < 6; there++)
		{
			if (adjacent[here][there] == 0) // 연결되지 않은 경우 무시
				continue;
			if (discovered[there]) // 이미 발견한 vertex인 경우 무시
				continue;

			q.push(there); // 방문 예약
			discovered[there] = true; // 발견 기록

			parent[there] = here; // 해당 vertex를 발견한 부모 vertex
			distance[there] = distance[here] + 1; // 시작 지점부터 방문할 vertex의 거리
		}
	}
}

 

 

 

 

 

 

 

 코드로 정리하면 위와 같다. DFS와 달리 Queue를 이용하는 형태로 구현되며 개인적으로 DFS보다 직관적이라 이해가 어렵지 않다고 생각한다. vertex의 방문 순서는 0->1->3->2->4의 순서이다.

 

 

 

 

 

 

 

 

 

 

 가중치가 일정한 그래프에서 최단 경로를 찾는 경우 DFS, BFS 알고리즘을 이용하여 찾는 것이 일반적이다. 다만 일반적으로 DFS보다는 BFS를 사용하는것이 좋다. DFS의 경우 방문할 수 있는 최대 지점까지 계속해서 파고 들어가는 식으로 vertex를 방문하는데 최악의 경우 그래프안의 모든 정점들을 방문한 후에야 최단 경로를 찾을 수 있는 반면에 BFS는 시작 지점으로부터 인접한 vertex들을 차례대로 방문하기 때문에 평균적인 최단 경로 발견시점이 DFS보다 빠르다.

 

 

 

 

 

 

 

 

 

 

 물론 최단 경로 탐색 문제에서 DFS가 유리한 경우의 수도 많지만 알고리즘 문제들 특성상 많은 예시들이 정답 검증에 사용되므로 최대한 많은 테스트에서 평균적으로 빠른 BFS를 사용하는게 올바른 경우가 많다.