Study/Algorithm 검색 결과
1 개의 검색 결과가 있습니다.
Study/Algorithm

DFS와 BFS (Python)

DFS와 BFS의 개념과 구현 공부 1. DFS (Depth First Search) 깊이 우선 탐색이다. 한 쪽을 끝까지 파고들고, 더 탐색할 수 없으면 한 노드씩 뒤로 돌아오며 탐색한다. 미로 탐색을 생각하면 된다. 한쪽으로 쭉 가다가, 막다른 길이 나오면 바로 전의 갈림길로 돌아가 다른 방향을 탐색한다. 탐색 과정에 제약이 있을 경우 DFS로 구현하는 것이 좋다. 1.1 DFS의 특징 1.1.1 DFS 장점 파고들고 있는 노드들만 기억하기 때문에 적은 메모리를 사용한다. 찾으려는 노드가 깊을 경우, BFS보다 빠르게 찾을 수 있다. 1.1.2 DFS 단점 해가 없는 경로를 탐색할 경우에도 단계가 끝날 때까지 탐색한다. (이를 방지하고 효율성을 높이기 위해 미리 지정한 조건까지만 탐색하고 빠져나오는 ..

2021. 3. 4. 19:16