Computer science/Data Structure (1) 썸네일형 리스트형 BFS vs DFS 요약 더보기 BFS와 DFS는 그래프에서 각 노드를 한 번씩만 방문하여 모든 노드를 방문하는 알고리즘이다. BFS의 장점 1. 너비 우선 탐색이기에 찾은 답이 최단 경로임을 보장 2. 어느 한 경로가 무한히 깊어져도 최단 경로 탐색 가능 BFS의 단점 1. 간선이 많아지면 많은 메모리가 필요함 DFS의 장점 1. 간선이 많아져도 메모리를 많이 차지하지 않음. 2. 정답 후보군을 미리 알고 있으면 BFS보다 빠르게 구할 수도 있음. 3. 사이클 감지에 효과적 DFS의 단점 1. 구한 답이 최단 경로임을 보장하지 않음. 그래프의 모든 노드를 방문하고 난 후에야 최단 경로임을 알 수 있음. 2. 어느 한 경로가 무한히 깊으면 빠져나오지 못함. BFS(Breadth First Search)와 DFS(Depth .. 이전 1 다음
