알고리즘 강의 | Do it! 알고리즘 코딩테스트 with Python - DFS

05-2 깊이 우선 탐색

- 그래프의 시작 노드에서 출발하여 탐색할 한 쪽 분기를 정하여 최대 깊이까지 탐색을 마친 후 다른 쪽 분기로 이동하여 다시 탐색을 수행하는 알고리즘

- 시간 복잡도: O(V+E), V는 노드의 수 E는 엣지의 수

- 응용 문제: 그래프 완전 탐색, 단절점 찾기, 단절선 찾기, 사이클 찾기, 위상 정렬

 

특징

- 재귀 함수로 구현, 스택 오버플로를 유의해야함

- 스택(FILO) 자료구조 이용

 

깊이 우선 탐색의 핵심 이론

- 한 번 방문한 노드를 다시 방문하면 안 되므로 방문 여부를 체크할 배열 필요

- 그래프는 인접리스트로 표현

- 탐색방식은 후입선출 특성을 가지므로 스택 사용(하지만 실제 구현에서는 스택 성질을 갖는 재귀 함수로 많이 구현)

 

동작 방식

1. DFS를 시작할 노드를 정한 후 사용할 자료구조(인접 리스트) 초기화하기

2. 스택에서 노드를 꺼낸 후 꺼낸 노드의 인접 노드를 다시 스택에 삽입하기

스택에서 노드를 꺼내서 인접리스트 확인, 인접 노드들을 스택에 삽입하고 방문 배열에 체크

3. 스택 자료구조에 값이 없을 때까지 반복하기

이미 다녀간 노드는 방문 배열을 바탕으로 재삽입하지 않는 것이 핵심

2의 과정 반복

> 스택에 노드를 삽입할 때 방문 배열을 체크하고, 스택에서 노드를 뺄때 탐색 순서에 기록하며 인접 노드를 방문 배열과 대조하여 살펴봄

 

구현

# 스택을 통한 DFS 구현
def dfs_iteration(graph, root):
	visited = [] # 방문배열
    stack = [root]
    
    while(stack):
    	node = stack.pop()
        
        if(node not in visited):
        	visited.append(node)
            stack.extend(graph[node])
	return visited

# 재귀를 통한 dfs 구현
def dfs_recursive(graph, start, visited, = []):
	visited.append(start)
    
    for node in graph[start]:
    	if node not in visited:
        	dfs_recursive(graph, node, visited)
	return visited

참고 사이트