GameStudy489 Chapter 03. 함수 개체 보호되어 있는 글 입니다. 2022. 1. 4. Chapter 16. Backtracking Note) DFS와 BFS의 단점 - DFS는 인접행렬의 크기가 커져서, 순회하는 트리의 구조가 깊어질수록 탐색이 상당히 느려지는 단점이 있음. - BFS의 경우, 인접행렬이 커질수록 큐의 크기도 기하급수적으로 커짐. 즉, 메모리의 사용량이 상당히 증가함. - 순회하는 트리의 깊이와도 상관없으며, 메모리 사용량도 줄일순 없을까? Def) Backtracking - 탐색하는 도중에, 지금의 서브 트리에 정답이 없을거 같다면 해당 서브 트리를 더이상 순회하지 않고 되돌아 가는 기법 - 이런 방식을 가지치기(Prunning)이라 함. - 어떤 노드의 유망성(Promising)을 판단하여, 유망하지 않다면 해당 노드를 가지치기하고, 부모 노드로 되돌아감(Backtraing) Note) Backtracking을 .. 2021. 12. 12. Chapter 15. BFS Def) 너비 우선 탐색(BFS, Breadth First Search) - 현재 정점과 인접한 모든 정점을 방문한 후, 다시 이들 정점과 인접한 모든 정점을 찾아 방문하는 방식. - 시작 정점으로부터 가까운 정점을 먼저 방문하고, 멀리 떨어진 정점을 나중에 방문. - 보통 큐를 이용하여 구현 Thm) BFS 구현 With 큐 #define _CRT_SECURE_NO_WARNINGS #include #include enum { FALSE = 0, TRUE = 1, MAX_COUNT = 101, }; typedef struct queue { intnArray[MAX_COUNT]; size_tuCnt; size_tuFront; size_tuRear; } queue_t; void enqueue(queue_t*.. 2021. 12. 2. Chapter 14. DFS Def) 그래프 순회(Graph Traversal) - 하나의 정점에서 시작하여 모든 정점들을 한 번씩 방문하는 작업 - 많은 문제들이 그래프 순회를 이용하여 해결될 수 있음. ex. 두 정점 사이의 연결 경로가 있는지 검사, 최단 거리 검사 등등 - 대표적인 그래프 순회 방법으로는 깊이 우선 탐색(Depth First Search), 너비 우선 탐색(Breadth First Search) Def) 깊이 우선 탐색(DFS, Depth First Search) - 현재 정점과 인접한 정점 중 하나를 선택하여 이동하는 과정을 반복. 더이상 이동할 정점이 없을 경우, 뒤쪽으로 백트래킹(Backtracking)하여 다시 이동할 경로를 탐색. - 시작 정점으로부터 거리가 멀어지는(깊이가 깊어지는) 방식으로 정점을.. 2021. 11. 28. 이전 1 ··· 92 93 94 95 96 97 98 ··· 123 다음
