BFS 썸네일형 리스트형 그래프 순회 (DFS & BFS) 종류 탐색방법 구현 방법 활용 시간복잡도 DFS 재귀, Stack 백트래킹 O(V^2) BFS Queue 최단경로 인접 리스트: O(V+E) 인접행렬: O(V^2) DFS (Depth First Search, 깊이 우선 탐색) 개념 한 루트에서 최대한 깊숙이 들어가면서 탐색한 후, 다시 돌아와 다른 루트로 탐색하는 방법 장단점 장점 단점 현 경로상의 노드들만 기억하면 되므로 저장 공간의 수요가 적다 해가 없는 경로에 깊이 빠질 가능성이 있음 목표 노드가 깊은 레벨에 있을 경우 해를 빨리 구할 수 있다. 얻어진 경로가 최단 경로라는 보장이 없다. 따라서, 최단경로를 구하기 위해서는 전체 경로를 다 돌아본 후 비교해야 한다. 구현 방법 재귀: 스택보다 속도는 빠르나 깊이가 너무 깊어지면 재귀 한도를 초과할 .. 더보기 이전 1 다음
