구름톤
-
[구름톤 챌린지 Week4(1)] 그래프 탐색 전략 (DFS, BFS)Challenges/구름톤 챌린지 2023. 9. 10. 07:56
이번 주차는 주로 그래프 탐색을 다뤄보았습니다. '탐색'을 어떻게 할지에 따라 알고리즘의 성능에 크게 차이가 나게 되다보니, 이를 위해 전략을 잘 짜는 것이 중요합니다. DFS (깊이 우선 탐색)과 BFS (너비 우선 탐색) 크게 두 가지를 정리하겠습니다. DFS (Depth-First Search, 깊이 우선 탐색) DFS는 깊이를 우선적으로 탐색하는 알고리즘입니다. 한 노드에서 시작하여, 해당 노드에 연결된 노드들 중 하나를 선택해 계속 '깊게' 탐색하고, 더 이상 탐색할 곳이 없을 경우 이전 노드로 돌아와 다른 노드를 탐색합니다. [자료구조] DFS는 스택이나 재귀 함수를 이용해 구현할 수 있습니다. BFS (Breadth-First Search, 너비 우선 탐색) BFS는 너비를 우선적으로 탐색하..