반응형 그래프1 DFS (깊이 우선 탐색, Depth-First Search) 알고리즘 - C언어, Java, Python 예시코드, 시간복잡도 DFS(Depth-First Search)는 그래프나 트리에서 널리 사용되는 탐색 알고리즘으로, 시작 정점에서 한 경로를 끝까지 탐색한 후에 다른 경로로 이동하는 방식으로 동작합니다. 모든 경로를 탐색하거나 특정 경로를 찾는 데 유용하며, 다양한 문제 해결에 활용됩니다.1. DFS의 개념DFS는 스택(Stack) 자료구조를 기반으로 하거나 재귀를 사용하여 구현되며, 그래프의 한 경로를 깊게 탐색한 후, 더 이상 탐색할 노드가 없을 때 이전 경로로 되돌아갑니다. 이를 "백트래킹(Backtracking)"이라고 합니다.(일반적으로 코딩테스트 문제 풀이 시 재귀로 dfs를 구현합니다.) 2. DFS의 동작 원리시작 정점을 방문하고 스택 또는 재귀 호출을 통해 탐색합니다.현재 정점의 인접 정점 중 방문하지 않은.. 2024. 12. 19. 이전 1 다음 반응형
