[알고리즘] DFS 알고리즘
정의 루트 노드에서 시작해서 다음 분기를 넘어가기 전에 해당 분기를 완벽하게 탐색하는 방법 DFS (Depth First Search) 약자로 한국어 표기로는 "깊이 우선 탐색" 이라고 한다. 장단점 장점 단지 현 경로상의 노드들만을 기억하면 되므로 저장 공간의 수요가 비교적 적다. 목표 노드가 깊은 단계에 있을 경우 해를 빨리 구할 수 있다. 단점 해가 없는 경로에 깊이 빠질 가능성이 있다. 얻어진 해가 최단 경로가 된다는 보장이 없다 코드 구현 def dfs(index, graph, visited): stack = [index] while stack: v = stack.pop() visited[v] = True for i in range(len(graph)): if visited[i] == False..
