DFS ; Depth-First-Search

DFS란 ?

그래프 탐색 방법 중의 하나로서 한 정점을 방문한 후에 그에 인접하고, 아직 방문하지 않은 한 정점을 선택하여 이로부터 다시 위 과정을 반복하는 방법.

이라고 네이버사전에 나와있군요-

자, 해당 알고리즘에서 사용될 그래프를 하나 그려보도록 할게요.

↙(?!)

...그림판이니 이해해 주세요^^;

이렇게 생긴 그래프가 하나있어요.

정점 1에서 시작해서 이동할수 있는 모든 접점을 찾아요.

DFS는 최단거리를 구하는 알고리즘이 아닌.

접근할수 있는 거리를 모두 구하는 알고리즘 입니다.

우리는 이 그래프에서 바로 1,4,7 이라는 경로를 A*와 같은 알고리즘 의 결과를 알고있지요?

[ A*로 예를들은것이며 이번글에는 DFS를 공부합니다. ]

그러나, 컴퓨터는 해당 그래프를 이해하지못해요.

그래서 우리가 배운 배열로 인접행렬을 만들어서 컴퓨터에게 인식시켜주어야 합니다.

가장먼저, 인접행렬부터 만들어볼게요.

int graph[N + 1][N + 1] = { // 0 1 2 3 4 5 6 7 {0, 0, 0, 0, 0, 0, 0, 0}, // 0 {0, 0, 1, 0, 1, 0, 0, 1}, // 1 {0, 1, 0, 1, 0, 0, 0, 0}, // 2 {0, 0, 1, 0, 0, 0, 0, 0}, // 3 {0, 1, 0, 0, 0, 1, 1, 0}, // 4 {0, 0, 0, 0, 1, 0, 0, 0}, // 5 {0, 0, 0, 0, 1, 0, 0, 0}, // 6 {0, 1, 0, 0, 0, 0, 0, 0} // 7 };

항상, 배열의 시작은 0부터 하지요.

그래서 인접행렬도 0부터 시작합니다.

1은 2,4,8이 열려있군요. 그러니 1행,1열의 2, 4, 8 행과 열에 1넣어줍니다.

왜 1을 넣어주느냐, 0은 막힌 길이며, 1은 열린 길이라고 처리합니다.

우리가 0을 False로, 1을 True로 배운것과 같이 기계어도 0을 False, 1을 True로 처리하지요.

그런데 N은 무엇이지요?

N은 따로 소개하지않은 상수값입니다.

#define N 7 으로선언되어있으며, 해당 인접행렬의 노드수를 뜻합니다.

자, DFS를 본격적으로 이용하기전. DFS의 원리를 설명해드리겠습니다.

가장먼저 1에서 출발을 합니다. 그다음 열린곳인 2, 4, 7중 2로 이동을 합니다. 해당 2에서 열린곳인 3으로 이동을 합니다. 3에서 열린곳이 2인데, 2는 이미 갔으니 1로 되돌아옵니다. 해당 1에서 열린곳인 4로 이동을 합니다. 4에서 열린곳이 5, 6 뿐이니 5로 먼저 접근을 합니다. 해당 5에서 열린곳이 4인데 4에서 갈곳이 6이 있기에 다시 4로 이동합니다. 해당 4에서 6으로 접근후, 더이상 갈곳이없으니 1로 넘어와서, 해당 1에서 7로 접근후 프로그램을 종료합니다. 그래서 콘솔에 표시되는 경로는 : 1->2, 2->3, 1->4, 4->5, 4->6, 1->7 이 됩니다.

이제 DFS의 몸통을 만들기전, DFS과 햇갈리기 쉬운 BFS를 잠시나마 말씀드리겠습니다.

BFS ( Breath First Search ) 는 일반적으로 큐의 방식을 사용합니다.

Queue 를 사용하기 위해서는 STL(Standard Template Library) 에서 제공하는 Queue를 사용하면 됩니다.

간단히 보여드리자면, queue<int> exq; 로 선언하게되면 queue를 사용한 int 형식의 exq 선언한다.

이런식의 코드가 됩니다. 그리고 exq.메서드 로 접근해서 해당 queue 를 사용이 가능합니다.

왜 갑자기 BFS를 알려주느냐?
DFS는 BFS와 달리 queue를 사용하는것이 아닌, Stack(스택)을 이용해서 구현합니다.

이로써 어느정도 기본기가 잡힌것 같으니 본격적으로 DFS의 몸통부분을 구현해보도록 할게요.

우리가 1박2일을 보면, 꼭 미션을 한뒤에 깃발을 꽂지요? 우리가 여기에 도착했다.

DFS도 마찬가지입니다. 나는 이곳을 지나쳤다. 라며 깃발을 꽂아줍니다.

int v[N + 1]={0,};

와 같이 v라는 변수를 통해 방문한 플래그를 처리해줍니다.

한번이라도 방문할경우에, 0에서 1로 설정합니다.

void DFSVisit(int i){

int j;

v[i] = 1; //해당 v 플래그에 방문했다는 표시를 합니다.

for(j=1; j<N+1; j++){

if(graph[i][j] == 1 && v[j] == 0){ //인접행렬의 [i][j] 구간이 막힌곳이 아니며(graph[i][j])

, 방문한적이 없는 (v[i]==0) 구간이면

printf("%d -> %d, ", i, j); //탐색후 경로를 찍어줍니다.

DFSVisit(j); //다음 노드를 재귀 탐색 합니다.

}

}

스택을 이용한다고 해놓고 재귀함수를 호출하였습니다.

당황하신분들도 있을것이며, 당황하지 않은분들도 계실것입니다.

재귀도, 스택의 한 종류입니다. 모르시고 계셨던분들은 이제 알아가면 됩니다!

코드는 따로 분석할 필요가없을듯해요.

주석이 모든 코드를 이해시켜주는군요.

마지막으로 메인부분을 보도록할게요.

void main()

{

DFSVisit(1); //1번부터 탐색시작

}

뭔가 복잡하면서도 간단하지요?

자, 이제 전체적인 코드를 투척후 공부하러 가겠습니다.

궁금한건 그때그때 질문해주세요.

바쁘면 답변못해드릴수도있어요..

출처 : http://cafe.naver.com/funcc/4490