728x90 BFS1 [알고리즘 이론] DFS와 BFS 더보기* DFS와 BFS 이해 전 그래프에 대한 이론을 알고 있다면 도움이 될 것이다. DFS 깊이 우선 탐색(Depth-First Seartch)는 그래프 완전 탐색 기법 중 하나이다. DFS는 그래프의 시작 노드부터 시작하여 탐색할 분기를 정하고, 끝까지 탐색 후 다음 분기로 넘어가서 다시 탐색하여 모두 다 탐색하는 알고리즘이다. DFS는 Stack 또는 재귀함수를 이용하여 구현할 수 있으며 시간 복잡도는 O(노드 수 + 에지 수)이다. 재귀함수를 사용할떈 스택 오버플로를 조심하며 사용해야한다. 우선 이런 그래프가 있다고 가정해보자. 이 그래프를 인접 리스트로 표현한다면 아래처럼 표현 할 수 있다. 1) 1부터 시작한다고 가정하고 1을 Stack에 넣음과 동시에 1이 들어 왔다는 것을 체.. 2023. 8. 1. 이전 1 다음 728x90
