DailyCode

깊이 우선 방식으로 정점을 방문하여 그래프를 탐색하는 그래프 탐색 알고리즘이다. 방문한 각 노드의 부모 노드를 추적하여 소스 노드와 그래프의 다른 노드 사이의 경로를 구성한다. 🚀 알고리즘 논리 DFS는 스택을 사용하여 방문한 노드를 추적한다. 소스 노드에서 시작하여 각 이웃 노드를 탐색하는 방식으로 작동한다. 🏁 알고리즘 동작 과정 시작점을 스택에 추가 스택이 비어있지 않다면, 스택에서 정점을 빼서 이웃 정점을 방문 이웃을 방문한 적이 없는 경우, 방문한 것으로 표시하고 스택에 추가한 후 2단계를 반복 이웃을 방문한 경우, 건너뛰고 2단계를 계속 진행 모든 정점을 방문했다는 것을 나타내는 스택이 비워질 때까지 2~4단계를 반복 (재귀적) ⏲ 시간 복잡도 O(V+E) (V: 노드의 수, E: 그래프의 가..

너비 우선 탐색(BFS) 다른 레벨로 이동하기 전에 같은 뎁스에 있는 모든 노드를 탐색하는 그래프 탐색 알고리즘 소스 노드에서 시작하여 그래프를 뎁스로 탑색하며, 다음 뎁스로 내려가기 전에 인접한 모든 노드를 방문한다. 개요 가중치가 없는 그래프에서 최단 경로를 찾거나, 특정 최적화에서 최적의 솔루션을 찾는데 널리 사용된다. 동작 과정 BFS 알고리즘은 큐(Queue) 자료구조를 이용하여 구현. 시작노드 선택 큐를 생성하고 시작노드를 큐에 대기 시작노드를 방문한 노드로 표기 큐가 비워질 때 까지 5,6 반복 큐에서 첫번째 노드를 큐에서 해제하고 방문한 노드로 표기 큐에 대기중인 노드 중 아직 방문하지 않은 인접 노드 모드 탐색, 그 후 이 노드들을 방문한것으로 표기하고 큐에 대기열 추가 모든 노드 방문시..