목록DFS (1)

개발자로 살아남기

깊이 우선 탐색 (DFS, Depth-First Search)

깊이 우선 탐색 깊이 우선 탐색 DFS (Depth-First Search) 깊이 우선 탐색 시 끝없이 깊어지는 것을 방지하기 위해 깊이 제한 적용 (조건을 이용) 목표 노드에 도달하지 못하면 부모노드로 되돌아감 (부모노드로 되돌아가는 것을 백트래킹(backtracking)이라고 함) 하나의 정점에서 아래쪽으로 깊게 탐색 후 더이상 탐색이 불가능하면 되돌아가 인접한 다른 노드를 탐색 시간 복잡도 : O(V + E) V : 정점의 개수 (위 사진에서 A, B, C, D, E, F, G) E : 간선의 개수 (각 정점을 잇는 선) 공간 복잡도 : O(V) 방문 여부를 확인하기 위한 visited 배열 추가 필요 방문 여부를 확인하기 위한 visited 배열 필요성 방문 여부를 체크하지 않으면 두 번 탐색할 ..
0x20. 알고리즘/0x21. 이론 2021. 10. 8. 16:44
이전 Prev 1 Next 다음