'Depth First Search'에 해당되는 글 1건

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

그래프, 어렵습니다. 그래프에 대한 이론은 많은 걸로 알고 있습니다. 그중에서 대표적인 것이 바로 탐색 기법인데요. DFS와 BFS라는 녀석, 이 둘이 가장 대표적입니다. 먼저 DFS(Depth First Search)라고 하는 놈이 있어요. 깊이 우선 탐색이라고 우리는 말하더군요! 이런 거는 역시 그림으로 한 방에 이해를 해버리는 게 좋거든요? 그래서 제가 그림을 하나 준비해왔답니다. 아래와 같은 무향그래프가 있다고 칩시다! 0에서부터 시작해서 모든 정점을 방문하려고 합니다. DFS탐색기법을 사용해서 정점을 방문할때 어떤 순서로 방문하게 될까요?

단, 규칙은 작은 노드순으로 방문한다는 조건으로요

이름답게 그 정점에서 아주 깊숙히 들어갑니다. 들어가서 더 이상 들어 갈 곳 없을 때까지 깊숙히 말입니다. 하지만 이미 방문된 노드라면 그 노드는 다시 방문하지 않습니다. 그럼 이제부터 탐색을 시작해 보겠습니다.

0에서부터 시작해서 노드번호가 작은 순으로 가려면 1을 방문해야겠지요?? 1과 인접한 가장 작은 노드 번호를 갖고 아직 방문하지 않은 노드는 2가 있네요. 2와 인접한 노드 중 가장 작고 방문하지 않은 노드는 4가 있습니다. 4는 더 이상 갈 곳이 없으므로 다시 돌아옵니다.

이제 3을 방문할 차례입니다. 1에 인접한 노드는 2와 3이었는 데 방금 2쪽 노드를 모두 방문했으니까요. 3은 인접한 노드가 1이 있는 데 이미 방문을 했답니다.

1로 다시 돌아와서 그 다음으로 인접한 노드를 찾아봅시다. 5가 있네요. 5에서 인접한 노드 중 방문하지 않고 가장 작은 노드는 6이 있습니다. 6은 이제 마지막 노드가 되겠습니다. 왜냐면 0도 방문했고 5도 방문했으니까요.

이것으로 모두 방문을 해보았습니다. 순서는 0 - 1 - 2 - 4 - 3 - 5 - 6 이렇게 되겠네요.

그림을 그려보면 이런 순서랍니다.

그렇다면 다음은 DFS를 코드로 구현해볼까요? 우리는 g라는 2차원 배열 변수로 그래프를 표현하게 됩니다. 바로 위와 같은 그래프입니다. 그리고 한가지 더 말씀드리자면 visited라는 변수를 통해서 그 정점이 방문이 되었는지 기록합니다. 이미 방문이 되면 더 이상 그 정점을 방문하면 안되니까요.

c 소스코드는 바로 아래와 같답니다.

#include <stdio.h>

#define N 7

int g[N][N]=
{
	{0,1,0,0,0,1,1},
	{1,0,1,1,0,0,0},
	{0,1,0,0,1,0,0}, 
	{0,1,0,0,0,0,0},
	{0,0,1,0,0,0,0},
	{1,0,0,0,0,0,1},
	{1,0,0,0,0,1,0}
};
int visited[N];
void dfs(int here) {

	//지금 here이 이미 방문된 정점이라면 다시 빠꾸
	if (visited[here]) return;

	printf("정점 %d를 방문\n", here);

	visited[here] = 1;	//지금 here 정점은 방문

	for (int next = 0; next < N; next++) 
		//그래프가 이어져있으면서, 아직 다음 정점이 방문되지 않았으면 ㄱㄱ
		if (g[here][next] == 1 && !visited[next]) dfs(next);
}
int main() {
	dfs(0);
}

결과는 이렇습니다.

네, 뭐 간단합니다. 재귀함수로 dfs를 쉽게 구현해볼 수 있습니다. 그렇다면 dfs를 도대체 어디에 활용할 수 있을까요? 배웠으면 써먹어야 될꺼 아니겠어요? 그런 다음 포스팅에 알아보도록 하겠습니다.