반응형 dfs1 [알고리즘] 깊이우선탐색(DFS)이란 ? 깊이우선탐색(DFS)이란? Depth First Search 그래프의 탐색방법중 한 가지로 시작한 노드에서 최대한 깊숙히(더 이상 갈곳이 없을때까지)탐색한 후 원점으로 돌아와서 다른 노드들을 탐색하는 방법입니다. 깊이우선탐색의 특징 자기 자신을 호출하는 순환 알고리즘 어떤 노드를 방문했는지를 반드시 체크해야한다. 체크하지 않으면 무한루프에 빠질 수 있다. 장점 구현이 간단하다. 현재 경로상의 노드만 기억하면 되므로 저장공간이 적게든다. 목표노드가 깊은곳에 있을경우에 빠르게 찾을 수 있다. 단점 단순 검색속도는 너비우선탐색보다 느리다. 해가 없는경우에 깊이 빠질 수 있다. 구한 경로가 최단경로가 아닐 수 있다. 실행순서 예시 구현 코드 import java.util.Scanner; public class .. 2020. 2. 5. 이전 1 다음
