Programming/알고리즘
-
깊이우선탐색 (DFS)Programming/알고리즘 2020. 11. 7. 16:24
스택을 사용할 수 있지만 재귀 또한 스택의 특성을 가지고 있으므로 더 빠른 프로그래밍을 위해 재귀를 사용하였다. 코드는 아래의 그래프를 참고하여 구현하였다. #include #include using namespace std; int n; int flag[8]; vector dfs[8]; void dfs_search(int start) { if (flag[start]) return; flag[start] = true; printf("%d ", start); for (int i = 0; i < dfs[start].size(); i++) { int x = dfs[start][i]; dfs_search(x); } } int main() { dfs[1].push_back(2); dfs[1].push_back(3..
-
너비우선탐색(BFS)Programming/알고리즘 2020. 11. 7. 16:03
너비우선탐색(Breadth first search, BFS)은 탐색을 할때 너비를 우선으로 탐색하는 기법이다. BFS는 '맹목적인 탐색 기법'에 속하며 '최단 경로'를 보장해줍니다. 또한, BFS는 자료구조인 Queue(FIFO)에 기반하여 구현할 수 있습니다. 코드는 아래와 같은 그래프를 기준으로 작성하였다. #include #include #include using namespace std; int n; int flag[8]; vector bfs[8]; queue q; void bfs_search(int start) { q.push(start); flag[start] = true; while (!q.empty()) { int x = q.front(); printf("%d ", x); q.pop(); ..