DFS(Death First Search) (1)

깊이 우선 탐색

개념

루트 노드(혹은 다른 임의의 노드)에서 시작해서 다음 분기(branch)로 넘어가기 전에 해당 분기를 완벽하게 탐색하는 방법

미로를 탐색할 때 한 방향으로 갈 수 있을 때까지 계속 가다가 더 이상 갈 수 없게 되면 다시 가장 가까운 갈림길로 돌아와서 이곳으로부터 다른 방향으로 다시 탐색을 진행하는 방법과 유사하다.

즉, 넓게(wide) 탐색하기 전에 깊게(deep) 탐색하는 것이다. 사용하는 경우: 모든 노드를 방문 하고자 하는 경우에 이 방법을 선택한다.

깊이 우선 탐색(DFS)이 너비 우선 탐색(BFS)보다 좀 더 간단하다. 단순 검색 속도 자체는 너비 우선 탐색(BFS)에 비해서 느리다.

자기 자신을 호출하는 순환 알고리즘의 형태를 가지고 있다.

그래프 탐색의 경우 어떤 노드를 방문 했는지 여부를 반드시 검사 해야한다.

이를 검사 하지 않을 경우 무한루프에 빠질 위험이 있다.

백준 문제