DFS(Depth-First Search) vs BFS(Breadth-First Search)

DFS (Depth-First Search)와 BFS (Breadth-First Search)는 그래프 또는 트리 탐색 알고리즘입니다. 두 알고리즘은 구조적 탐색을 수행하지만 서로 다른 방식으로 그래프나 트리의 노드를 탐색합니다.DFS (Depth-First Search)DFS는 가능한 깊이까지 탐색을 진행한 후, 더 이상 진행할 수 없으면 다시 돌아와 다른 경로를 탐색하는 방식입니다.특징:Stack 사용: 일반적으로 재귀(내부적으로 스택 사용) 또는 명시적 스택을 사용하여 구현합니다.깊이 우선 탐색: 현재 노드의 자식들을 모두 방문한 후, 다른 자식들을 방문합니다.경로 탐색: 특정 경로가 있는지 확인하거나, 트리의 깊이를 계산할 때 유용합니다.구현:def dfs(graph, start, visited=..
코딩테스트 2024. 5. 20. 14:41
1