너비우선탐색1 [ 알고리즘 ] DFS와 BFS DFS(Depth First Search, 깊이 우선 탐색)란? 루트 노드(혹은 다른 임의의 노드)에서 시작해서 다음 분기(branch)로 넘어가기 전에 해당 분기를 완벽하게 탐색하는 방법으로 스택 또는 재귀 호출을 이용한다. 1. 미로를 탐색할 때 한 방향으로 갈 수 있을 때까지 계속 가다가 더 이상 갈 수 없게 되면 다시 가장 가까운 갈림길로 돌아와서 이곳으로부터 다른 방향으로 다시 탐색을 진행하는 방법과 유사함 2. 즉 넓게(wide) 탐색하기 전에 깊게(deep) 탐색함 3. 모든 노드를 방문하고자 하는 경우에 이 방법을 선택함 4. 깊이 우선 탐색(DFS)이 너비 우선 탐색(BFS)보다 좀 더 간단함 5. 검색 속도 자체는 너비 우선 탐색(BFS)에 비해서 느림 DFS의 과정 DFS의 시간 복잡.. 2021. 1. 4. 이전 1 다음
