[이론] DFS- (2) 재귀로 구현하기

 

 

 

목차

---

 

이전 글에서는 DFS를 스택으로 구현했다면, 이번에는 더 널리 사용되는 방식인 DFS를 사용해서 구현해보자. 

이전글 에서 기본 개념과 스택 구현 방법을 확인해보세요. 

[이론] DFS- (1) 스택으로 구현하기

 

 

 

학습 목표 

- python 으로 재귀 기반 DFS를 구현할 수 있다. 

- DFS의 재귀적인 성질을 이해한다. 

 

DFS와 재귀 

 

DFS는 그래프를 탐색할 때 한 노드에서 출발하여 가능한 깊이 들어가서 탐색한 다음, 더 이상 탐색할 노드가 없으면(리프 노드)

다시 이전 노드로 돌아와서(백트래킹) 다른 경로를 가능한 깊이 탐색한다. 

 

재귀 함수의 경우 동일한 알고리즘으로 적용하여 큰 문제를 작은 하위 문제로 나누어 가면서 풀 수 있을 때 사용한다. 

즉, 깊이 우선 탐색도 더이상 탐색할 노드가 없을 때, 백트래킹하여 다른 서브트리에 깊이 우선 탐색을 진행하므로 재귀적인 성격이 있다. 

 

수도 코드 

 

1. 시작 노드 a를 방문 처리함

2. a 노드의 인접 노드를 모두 순회.

-  a의 주변 노드를 모두 방문했다면 탐색을 멈춘다.

-  a의 주변 노드 중 방문하지 않은 노드 b가 있을 때

• a의 주변 노드를 모두 방문하기 전, 방문하지 않은 노드 b의 subtree를 모두 방문함. ⇒ 깊이 우선 탐색
• b의 subtree를 모두 방문했을 때는 다시 노드 a로 돌아가(backtracking) 주변 노드 중 방문하지 않은 노드 c를 방문한다.

코드 

재귀함수를 짤 때는 3가지 구현 조건이 있음을 유의하고 구현하도록 한다. 

 

+ 재귀 함수를 실제 구현할 때 고려하면 좋은 점

- 종료 조건, 함수 인자를 어떤 것을 쓸 것인지, 값을 어떤 형태로 리턴할 것인지/아니면 값을 인쇄할 것인지 

# 그래프 정의
graph = dict()

# key: 부모노드, value: 자식 노드 리스트
graph['A'] = ['B', 'C']
graph['B'] = ['A', 'D']
graph['C'] = ['A', 'G', 'H', 'I']
graph['D'] = ['B', 'E', 'F']
graph['E'] = ['D']
graph['F'] = ['D']
graph['G'] = ['C']
graph['H'] = ['C']
graph['I'] = ['C', 'J']
graph['J'] = ['I']


def DFS_recursion(graph, node, visited):
    # 종료 조건: 그래프의 모든 노드를 방문했을 때
    visited.append(node)

    # 아닐 경우
    for adj_node in graph[node]:
        if adj_node not in visited:
            DFS_recursion(graph,adj_node, visited)
    return visited


print(DFS_recursion(graph, 'A', []))
# ['A', 'B', 'D', 'E', 'F', 'C', 'G', 'H', 'I', 'J']

 

 

 

 

---

Reference

 

 

 

DFS 완벽 구현하기 [Python]

 

재귀 알고리즘을 사용하는 3가지 단계