이론
-
[알고리즘] 너비 우선 탐색 (BFS, Breadth-First Search)Algorithm 2020. 12. 11. 19:13
너비 우선 탐색 (BFS, Breadth-First Search)는 그래프 탐색 방법 중 한 정점에서 시작하여 모든 정점을 탐색하기 위한 방법이다. 너비 우선 탐색은 현재 위치를 기준으로 사방으로 퍼져나가면서 탐색하는 방법으로, 인접한 정점들을 먼저 탐색한 후에 차례로 탐색을 진행한다. 장점 모든 가중치가 동일할 때, 시작 정점으로 부터 목표까지 최단 경로를 보장한다. 단점 정점의 수가 늘어날 수록 탐색에 불필요한 정점을 저장해야 하기 때문에 저장공간이 비교적 많이 필요하다. 주로 두 정점 사이의 최단 경로나 임의의 경로를 찾을 때 사용한다. 점점 탐색 범위를 확장하며 탐색하기 때문에 처음 발견하는 경로가 최단 경로가 된다. 주의할 점은 DFS와 마찬가지로 방문 체크가 필요하다. 그림으로 이해하면 쉽기 ..
-
[알고리즘] 깊이 우선 탐색 (DFS, Depth-First Search)Algorithm 2020. 12. 10. 18:48
깊이 우선 탐색 (DFS, Depth-First Search)는 그래프 탐색 방법 중 한 정점에서 시작하여 모든 정점을 탐색하기 위한 방법이다. 깊이 우선 탐색은 간단하게 "한쪽 방향으로 파고들어 탐색하는 방식"으로 미로에서 길을 찾는 것과 같다. 시작점으로부터 다음 분기로 넘어가기 전에 해당 분기를 완벽하게 탐색한다. 장점 현 경로상의 노드만 저장하면 되기 때문에 그래프 높이 만큼의 저장공간을 필요로 한다. 즉, 최대저장공간의 수요가 비교적 적다. 목표가 위한 깊이가 깊을 경우 해를 빠르게 구할 수 있다. 단점 해가 없는 경로에 깊이 빠질 수 있다. 목표에 이르는 경로가 다수인 경우, 목표에 닿으면 팀색을 끝내기 때문에 최적의 해가 아닐 수 있다. 주로 모든 경로를 탐색해야하거나, 경로 탐색에 조건이 ..