[파이썬] 깊이 우선 탐색 (DFS)의 개념과 구현
깊이 우선 탐색 (Depth-First Search, DFS)은 그래프를 탐색하는 알고리즘 중 하나로, 한 노드에서 시작하여 해당 노드의 자식 노드를 우선적으로 탐색하는 방식입니다.
DFS는 스택 또는 재귀 함수를 사용하여 구현할 수 있으며, 탐색 과정에서 노드를 방문하고, 해당 노드의 자식 노드를 방문하기 전에 그 노드를 깊이 탐색하는 특징을 가지고 있습니다.
DFS의 구현
다음은 DFS를 구현하는 Python 코드입니다.
def dfs(graph, start_node):
visited = [] # 방문한 노드를 저장하는 리스트
stack = [start_node] # 탐색할 노드를 저장하는 스택
while stack: # 스택이 비어있을 때까지 반복
node = stack.pop() # 스택에서 가장 위에 있는 노드를 꺼냄
if node not in visited: # 해당 노드가 방문되지 않았다면
visited.append(node) # 노드를 방문한 것으로 처리
for neighbor in graph[node]: # 현재 노드의 인접 노드들을 스택에 추가
stack.append(neighbor)
return visited
DFS의 예시
다음은 DFS 알고리즘을 이용하여 그래프를 탐색하는 예시입니다.
graph = {
'A': ['B', 'C'],
'B': ['D', 'E'],
'C': ['F'],
'D': [],
'E': ['F'],
'F': []
}
start_node = 'A'
result = dfs(graph, start_node)
print(result)
출력:
['A', 'C', 'F', 'E', 'B', 'D']
위 예시에서는 ‘A’ 노드를 시작 노드로 설정하고, 주어진 그래프를 DFS 알고리즘을 이용하여 탐색합니다. 탐색 결과로는 ‘A’, ‘C’, ‘F’, ‘E’, ‘B’, ‘D’ 순서로 노드를 방문한 순서가 출력됩니다.
DFS는 특정 노드에서 출발하여 모든 노드를 탐색할 때 유용한 알고리즘입니다. 주어진 그래프가 크고 복잡할 때, 재귀 함수를 사용하는 구현 방식은 스택 오버플로우 에러가 발생할 수 있으므로, 스택을 이용한 방식이 더 안전한 선택일 수 있습니다.