08. 깊이 우선 탐색

깊이 우선 탐색의 정의

• Depth First Search는 깊이를 우선적으로 탐색하는 알고리즘
• 전체 노드를 맹목적으로 탐색하고자 할 때 사용
• 스택 자료구조에 기초

깊이 우선 탐색은 모든 경우의 수를 탐색하고자 할 때 쉽게 사용

깊이 우선 탐색의 순서

1. 탐색 시작 노드를 스택에 삽입 후 방문처리
2. 스택 최상단 노드에 방문하지 않은 인접 노드가 하나라도 있으면 그 노드를 스택에 넣고 방문처리
3. 방문하지 않은 인접 노드가 없으면 스택에서 최상단 노드를 꺼냄
4. 위의 과정을 더 이상 수행할 수 없을 때까지 반복

방문 순서 : 1 - 2 - 7 - 6 - 8 - 3 - 4 - 5

깊이 우선 탐색의 구현

#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
#include <stdlib.h>
#define MAX_SIZE 1001

// 노드 구현
typedef struct {
	int index;
	struct Node* next;
} Node;

// 연결 리스트
Node** a;
// 정점과 간선, 스택
int n, m, c[MAX_SIZE];

// 삽입 함수
void addFront(Node* root, int index) {
	Node* node = (Node*)malloc(sizeof(Node));
	node->index = index;
	node->next = root->next;
	root->next = node;
}

void dfs(int x) {
	if (c[x]) return;
	c[x] = 1; // 방문 처리
	printf("%d ", x);
	Node* cur = a[x]->next;

	// 탐색할 다음 노드가 없을 때까지 진행
	while (cur != NULL) {
		int next = cur->index;
		dfs(next); // 재귀적으로 반복
		cur = cur->next;
	}
}

// 방문 순서에 대해서는 기준 정립 x
int main(void) {
	// 정점과 간선 입력
	scanf("%d %d", &n, &m);
	a = (Node**)malloc(sizeof(Node*) * (MAX_SIZE));
	// 초기화
	for (int i = 1;i <= n;i++) {
		a[i] = (Node*)malloc(sizeof(Node));
		a[i]->next = NULL;
	}
	// 정점들을 연결하는 간선 입력
	for (int i = 0;i < m;i++) {
		int x, y;
		scanf("%d %d", &x, &y);
		addFront(a[x], y);
		addFront(a[y], x);
	}

	dfs(1);
	system("pause");
	return 0;
}

DFS는 스택 구조에 기초하므로 구현이 간단 탐색 수행 시 O(N) 시간 소요