728x90 시간 복잡도1 깊이 우선 탐색(DFS; Depth-First Search) 루트 노드(혹은 다른 임의의 노드)에서 시작해서 다음 분기(branch)로 넘어가기 전에 해당 분기를 완벽하게 탐색하는 방법 ex) 미로를 탐색할 때, 한 방향으로 갈 수 있을 때까지 계속 가다가 더 이상 갈 수 없게 되면다시 가장 가까운 갈림길로 돌아와서 이곳으로부터 다른 방향으로 다시 탐색을 진행하는 방법과 유사넓게 탐색하기 전에 깊에 탐색하는 방법DFS가 BFS보다 좀 더 간단단순 검색 속도 : 너비 우선 탐색에 비해 느림 사용하는 경우모든 노드를 방문하고자 하는 경우 특징자기 자신을 호출하는 순환 알고리즘 형태전위 순회(Pre-Order Traversals)를 포함한 다른 형태의 트리 순회는 모두 DFS의 한 종류*어떤 노드를 방문했었는지 여부를 반드시 검사해야 함.(이를 검사하지 않는 경우, 무.. 2025. 1. 21. 이전 1 다음 728x90
