[DS] 깊이 우선 탐색(DFS, Depth First Search)

깊이 우선 탐색이란 그래프나 트리에서 사용되는 탐색 알고리즘이다.

특징

• stack구조 이용
• 탐색 방식(흐름)
  1. 한 정점에서 한 방향으로 갈 수 있는 최대한의 깊이 까지 내려간다.
  2. 더 이상 갈 곳이 없을 경우 이전으로 돌아간다.
  3. 이동할 수 있는 다음 경로를 창다 탐색한다.

1. 탐색 방법

- 탐색 규칙

1. 출발 정점을 정한다.
2. 인접한 정점을 검사하여 낮은 인덱스를 전진할 정점으로 정한다.
3. 방문 표시(F→T)를 하고 현재 정점을 스택에 저장하고 전진한다.
4. 전진할 정점이 없으면 스택에서 pop하여 2.로 가서 반복한다.
   만약 스택이 비어 있다면 탐색을 완료한다.
   
   

- 탐색 과정

• A에서 부터 시작한다고 하자.
• 인덱스 번호가 낮은 인접을 방문한다.
  그러면 A → B → D → G → E → F → C 순으로 이동한다.
  

top의 순서 : 0 → 1 → 2 → 3 → 4 →3 → 2 → 1 →0 → -1

- 코드

#include <stdio.h>
#define SIZE 8

typedef enum{false, true} bool; 
//0부터 번호가 부여되기 때문에 flase부터 사용 //{true=1, false=0}와 같다.
//typedef : 새로운 이름을 만들자, 우리가 원하는 특별한 이름 'bool'을 만들려고 할때
// enum : 열거형, 여러 가지 선택지를 나영해 놓은 것을 의미 (true, false)
// {false, ture} : 선택할 수 있는 것들. 두 가지 값 중 하나를 골라 사용할 수 있음
//bool : 'bool'이라는 새로운 이름을 사용해서 '참과 거짓을 구분하는 자료형'을 쉽게 표현할 수 있게됨.

int stack[SIZE];
int top = -1;  //top의 위치 변화 : -1 -> 0 -> 1 -> ...
void push(int index) {
	stack[++top] = index;
}

int pop(void) {
	if (top == -1) return -1;
	return stack[top--];
}

void DepthFirstSearch(char V[], bool G[][SIZE]) {
	int i, j;
	char startVertex;  //탐색을 시작할 노드를 사용자가 입력
	bool searchOK[SIZE] = { false };  //각 노드의 방문 여부를 기록하는 배열로, 노드가 방문되면 true로 설정됨.
	printf("출발 정점: "); scanf_s("%c", &startVertex, 1); //1은 버퍼처리를 위해 씀
	for (i = 0; i < SIZE; i++) if (V[i] == startVertex) break; 
	printf("깊이 우선 탐색:  %c", startVertex);
	searchOK[i] = true; 
	do {
		for (j = 0; j < SIZE; j++) {
			if (G[i][j] == 1 && searchOK[j] == 0) { //1대신 true, 0대신 false 사용 가능
				printf("-> %c", V[j]);
				searchOK[j] = true;
				push(i); //
				i = j;
				break;
			}
		}
		if (j == SIZE) i = pop();
	} while (i>=0);
}

int main(void) {
	char V[] = { 'A', 'B', 'C', 'D', 'E', 'F', 'G', 'H' };
	bool G[SIZE][SIZE] = { {0,1,1,0,0,0,0,0},  //A
						   {1,0,0,1,1,0,0,0},  //B
						   {1,0,0,0,0,1,1,0},  //C
						   {0,1,0,0,0,0,0,1},  //D
						   {0,1,0,0,0,0,0,1},  //E
						   {0,0,1,0,0,0,0,1},  //F 
						   {0,0,1,0,0,0,0,1},  //G
						   {0,0,0,1,1,1,1,0} }; //H
						//  A B C D E F G H
	DepthFirstSearch(V, G);
	return 0;
}