깊이 우선 탐색1 [Java] DFS 깊이 우선 탐색 - 인접리스트 / 인접행렬로 구현 DFS 깊이 우선 탐색 (Depth Fisrt Search) "더 나아갈 길이 보이지 않을 때까지 깊이 들어간다"를 원칙으로 그래프 내의 정점을 방문하는 알고리즘이다. 미로 찾기처럼 그래프의 정점을 타고 깊이 들어가다가 더 이상 방문해왔던 정점 말고는 다른 이웃을 갖고 있지 않은 정점을 만나면 뒤로 돌아와 다른 경로로 뻗어있는 정점을 타고 방문을 재개하는 방식으로 동작한다. * 루트 노드(혹은 다른 임의의 노드)에서 시작해서 다음 분기(branch)로 넘어가기 전에 해당 분기를 완벽하게 탐색하는 방법 * 사용하는 경우: 모든 노드를 방문하고자 하는 경우에 이 방법을 선택한다. (완전 탐색 알고리즘에 자주 이용됨) DFS의 특징 자기 자신을 호출하는 순환 알고리즘의 형태 트리 순회(전위, 중위, 후위 순회.. 2020. 4. 25. 이전 1 다음 반응형
