[알고리즘] DFS(Depth First Search) 깊이 우선 탐색

코딩테스트에서 자주 쓰이는 알고리즘 중 하나입니다. 트리 구조에서 목표 노드까지 깊이 우선 탐색해 빠르게 목표 노드까지 갈 수 있는 알고리즘 중 하나죠 이와 비슷한 알고리즘 중 하나인 BFS란 알고리즘도 있는데 그 알고리즘은 너비 우선 알고리즘 으로써 큐 자료구조를 사용하고 DFS는 스택 자료구조를 사용합니다.

DFS는 일반적으로 재귀 함수를 이용합니다. 목차 1 .

스택 자료구조의 이해 2 . DFS의 특징 3 .

DFS 코드 예제 (C언어) 4 . DFS 문제들 (백준) 1-1 스택이란?

스택(Stack)은 쉽게 프링글스 과자 통을 생각해 봅시다. 과자통이 있고 맨 위쪽부터 맨 아래쪽까지 과자가 들어 있죠 이 상황속 저희가 과자를 어떻게 먹죠?

위에서 부터 먹습니다. 즉 맨 아래쪽에 있는 과자를 먹기.....