DFS

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

루트 노드(혹은 다른 임의의 노드)에서 시작해서 다음 분기(brach)로 넘어가기 전에 해당 분기를 완벽하게 탐색하는 방법.

보통 DFS는 특정 도시에서 다른 도시로 갈 수 있는지 없는지, 전자 회로에서 특정 단자와 단자가 서로 연결되어 있는지 등에서 많이 쓰인다.

• 미로를 탐색할 때 한 방향으로 갈 수 있을 때까지 계속 가다가 더 이상 갈 수 없게 되면 다시 가장 가까운 갈림길로 돌아와서 이곳으로부터 다른 방향으로 다시 탐색을 진행하는 방법과 유사
• 넓게(wide) 탐색하기 전에 깊게(deep) 탐색하는 것이다.
• 모든 노드를 방문 하고자 하는 경우에 이 방법을 선택.
• 단순 검색 속도 자체는 너비 우선 탐색(BFS)에 비해서 느리다.

깊이 우선 탐색(DFS)의 특징

• 자기 자신을 호출하는 순환 알고리즘의 형태를 가짐.
• 전위 순회(Pre-Order Traversals)를 포함한 다른 형태의 트리 순회는 모두 DFS의 한 종류.
• 그래프 탐색의 경우 어떤 노드를 방문했었는지 여부를 반드시 검사해야함.
  • 이를 검사하지 않으면 무한루프에 빠질 위험이 있다.

첫 번째 예시

• 각 노드들이 누구누구랑 연결되어있는지 확인하기 위해 2차원 배열인 arr를 만들어서 연결된 노드들은 1로 바꿔준다. 그리고 DFS를 실행
• 각 검사할 노드들은 for문으로 7까지 나열되며, 깊이는 7이다.
• 이것을 통해 방문하는 곳을 순서대로 나열한다.

#include <stdio.h>

int n, cnt = 0;
int arr[11][11]; // 노드 연결 확인
int visit[200]; // 방문여부체크

void DFS(int depth)
{
	visit[depth] = 1; cnt++;
	//printf("visit[%d] : %d\\n", depth, visit[depth]);
	for (int i = 1; i <= n; i++)
	{
		if (arr[depth][i] == 1 && visit[i] == 0)
		{
			printf("DFS IN i : %d\\n", i);
			DFS(i);

			//printf("DFS OUT i : %d\\n", i);
		}
	}
}

int main()
{
	n = 7;
	arr[1][3] = 1;
	arr[3][1] = 1;
	arr[3][5] = 1;
	arr[5][3] = 1;
	arr[5][7] = 1;
	arr[7][5] = 1;
	arr[1][2] = 1;
	arr[2][1] = 1;
	arr[2][4] = 1;
	arr[4][2] = 1;
	arr[4][8] = 1;
	arr[8][4] = 1;
	printf("DFS IN i : %d\\n", 1);
	DFS(1);
}

결과

./a.out 
DFS IN i : 1
DFS IN i : 2
DFS IN i : 4
DFS IN i : 3
DFS IN i : 5
DFS IN i : 7

자료

[알고리즘] 깊이 우선 탐색(DFS)이란 - Heee's Development Blog

[알고리즘] 깊이 우선 탐색(DFS)이란 - Heee's Development Blog