728x90
dfs
-
Backtracking(백트래킹)과 DFS의 차이점Interview 2025. 3. 17. 23:43
1. DFS (Depth-First Search, 깊이 우선 탐색)DFS는 그래프 탐색 알고리즘 중 하나로, 한 경로를 끝까지 탐색한 후 다른 경로를 탐색하는 방식입니다.보통 재귀(Recursion)나 스택(Stack) 을 사용하여 구현합니다.그래프 탐색에서 특정 노드를 방문한 후, 그 자식 노드들을 방문하는 방식입니다.DFS는 모든 가능한 경우를 무조건 탐색하는 경우가 많습니다.예시: 그래프에서 DFS 탐색graph = { 1: [2, 3], 2: [4, 5], 3: [6], 4: [], 5: [], 6: []}visited = set()def dfs(node): if node in visited: return visited.add(node) ..