[알고리즘] 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:
				stack.append(i)
	return visited	

DFS vs BFS 비교

그림으로 보면 차이점이 명확해질 것이다.

출처 : 나무위키