DFS(Depth First Search)

이건 BFS 와는 다르게 깊이 우선 탐색이다.

BFS라면 1, 2, 3.... 순이겠지만, DFS는 1, 2, 4..... 순이다.

코드는 다음과 같다.

void dfs(int num) {
	if(check[num]) return;
	check[num] = true;
	cout << num << ' ';
	for(int i = 0; i < arr[num].size(); i++) {
		int y = arr[num][i];
		dfs(y);
	}
}

BFS보다 짧다....?!?!??!?

는 재귀 함수 덕분이지 ㅠ

 

방법도 간단하다. 원래는 stack을 쓰는데 CPU는 이를 기반으로 한다고 해서 굳이 선언 해줄 필요는 없다고 한다.

계속 재귀함수로 돌아가면서 아닌건 버리고 맞는것만 골라서 출력해주는 느낌이랄까..!!!

 

DFS도 생각보다.... 사용이 어려웠다...ㅠㅠㅠㅠㅠㅠㅠㅠ