알고리즘 | 깊이우선탐색(DFS) 정리

알고리즘 | 깊이우선탐색(DFS) 정리

◼ 깊이우선탐색이란?

=DFS (Depth Fist Search)

넓이를 우선적으로 탐색 한다는 것을 의미한다.

시작 정점으로부터 가까운 정점을 먼저 방문하고,

멀리 떨어져 있는 정점을 나중에 방문하는 순회방법.

맹목적 탐색 방법의 하나로

경우의 수를 조사하고 -> 또 그 다음 경우의 수를 조사하면서 답을 찾는 과정으로서,

두 노드 사이의 최단 경로 혹은 임의의 경로를 찾고 싶을 때 많이 사용하는 방법.

좌측의 애니메이션 예시를 보면 이해가 쉽습니다.

미로를 탐색할 때 한 방향으로 갈 수 있을 때까지 계속 가다가

더 이상 갈 수 없게 되면 다시 가장 가까운 갈림길로 돌아와

다른방향으로 다시 탐색을 진행하는 방법이죠.

(이미지 출처 : 위키백과)

기억하자! 깊이우선탐색은 미로탐색~

◼ 깊이우선탐색의 장단점

◾ 장점

◽ 저장공간의 수요가 비교적 적다.

◽ 목표노드가 깊은 단계에 있을 경우 답을 빨리 구할 수 있다.

◾ 단점

◽ 답이 다른 경로에 있는데도 불구하고 깊숙히 빠질 가능성이 있다.

◽ 최단 경로가 된다는 보장이 없다.

깊이우선 탐색은 답에 다다르면 탐색을 끝내버리므로, 이때 얻어진 답은 최적이 아닐 수도 있다.

from http://babodocoding.tistory.com/49 by ccl(A) rewrite - 2021-12-27 16:00:37