깊이 우선 탐색
-
[Graph] 그래프의 탐색 - 깊이 우선 탐색 (DFS, Depth-First Search)알고리즘, 코딩테스트/알고리즘 개념 2023. 12. 5. 02:12
알고리즘 문제에서 가장 큰 비중을 차지하는 유형 중 하나가 바로 그래프 탐색 문제다. 어떤 형태의 코딩 테스트, 알고리즘 시험에서든 가장 쉽게 만날 수 있는 문제 유형이기도 하고 여러 문제가 출제되는 형식이라면 반드시 한문제 이상 포함된다고 할 수 있을 정도다. 그래프 탐색 알고리즘은 필수 중 필수이기 때문에 반드시 익숙해져야 한다. 깊이 우선 탐색 (DFS, Depth-First Search) DFS는 대표적인 그래프 탐색 알고리즘 중 하나다. 직관적인 이름 그대로 깊이를 따라서 탐색해나가는 방법으로 너비 우선 탐색(BFS)과 대조되는 특징을 가진다. BFS의 경우 동시에 여러 갈래의 길을 뻗어나가듯 탐색한다면 DFS는 일반적으로 미로찾기를 해나갈 때와 같이 분기점에서 하나의 길을 선택하고 그 길을 따..