[알고리즘] 깊이 우선 탐색(Deep First Search, DFS)
1. 깊이 우선 탐색
1) 개념 정리
- 첫 시작을
start라고 했을 때, 더 이상 탐색할 수 없을 때까지 계속 탐색하는 과정을 말한다.
트리라고 생각했을 때, 부모 노드에서 자식 노드로 계속해서 탐색하는 과정이다. - 스택(Stack)으로 푸는 방법과 재귀함수(Recursion Function)으로 푸는 방법 2가지가 있다고 한다.
2) 탐색 과정
준비물 : visited 변수
가장 끝에 있는 원소를 추출하면서 그와 동시에 stack에 후보가 될 수 있는 정점을 계속해서 추가한다.
3) 코드 구현
위의 그림을 예시로 코드를 구현해보았다.
Stack으로 풀기
# 스택으로 DFS 구현
def dfs_stack(graph,start):
stack = [start]
visited = []
while stack:
node = stack.pop()
if node not in visited:
visited.append(node)
stack.extend(graph[node])
print(f'stack {stack}')
print(f'visited {visited}')
return visited
재귀함수(Recursive Function)
# 재귀함수로 DFS 구현
def dfs_recursive(graph,start):
visited = []
def dfs(node):
if node not in visited:
visited.append(node)
print(f'visited {visited}')
for n in graph[node][::-1]:
dfs(n)
dfs(start)
return visited
- Note! 재귀함수를 사용할 때에는
RecursionError를 조심해야 한다. 만약 이 에러를 만났다면 다음 코드로 해결할 수 있다.sys.setrecursionlimit(int)
댓글남기기