[알고리즘] 깊이 우선 탐색(DFS, Depth First Search)이란? 깊이 우선 탐색(DFS, Depth-First Search) 트리나 그래프의 하나의 정점의 특정 노드에서 시작해서 다음 분기로 넘어가기 전에 해당 분기를 깊게 전부 먼저 탐색해 나가는 방법입니다. 마치 미로에서 갈수있는 끝까지 갔다가 가장 가까운 갈림길에서 다시 탐색을 시작하는 방법과 유사합니다. 왼쪽 그림과 같이 하나의 노드의 모든 루트를 깊게(deep) 탐색하고 다음 노드로 넘어가는 깊이우선탐색(DFS)과 오른쪽처럼 달리 동일한 깊이를 먼저 넓게(wide) 탐색하는 것을 볼 수 있습니다. 깊이 우선 탐색(DFS)의 특징 DFS는 일반적으로 스택이나 재귀호출을 통해 구현합니다. (재귀호출을 통한 메서드 스택) 리프노드를 한 번에 잘라내기 용이하여 백트래킹 알고리즘에 자주 사용됩니다. 어떤 노드를 방문했.. 알고리즘/이론 2022. 3. 7. 06:21
[알고리즘] 너비 우선 탐색(BFS, Breadth-First Search)이란? 너비 우선 탐색(BFS, Breadth-First Search) 트리나 그래프의 하나의 정점에서 시작해서 정점에 인접한 모든 노드를 먼저 탐색하고 멀리 떨어져 있는 정점을 나중에 방문하는 순회 방법으로 주로 두 노드 사이의 최단 경로를 찾고 싶을 때 이 방법을 선택합니다. BFS 탐색과정 루트에서 시작한다. 자식 노드들을 [1]에 저장한다. [1]에 저장된 노드들을 차례로 방문한다. 또한 각각의 자식들을 [2]에 저장한다. [2]에 저장된 노드들을 차례로 방문한다. 또한 각각의 자식들을 [3]에 저장한다. 위의 과정을 반복한다. 모든 노드를 방문하면 탐색을 마친다. 왼쪽 그림과 같이 하나의 노드의 모든 루트를 깊게(deep) 탐색하고 다음 노드로 넘어가는 깊이우선탐색(DFS)과 오른쪽처럼 달리 동일한 깊.. 알고리즘/이론 2022. 1. 12. 13:48
