파이썬으로 DFS 구현하기

DFS란?

깊이 우선 탐색(Depth First Search, DFS)이란 말로써, 가장 깊은 곳부터 먼저 탐색하고, 차례대로 낮은 순을 찾아가는 방법이라고 보면 된다.

DFS의 활용 예

1. 경로 찾기: 특정 노드에서 다른 노드까지의 경로를 찾는 데 유용합니다.
2. 사이클 탐지: 그래프에 사이클이 존재하는지 확인하는 데 사용됩니다.
3. 토폴로지 정렬: 방향 그래프에서 정점들을 선형으로 정렬하는 데 사용됩니다.
4. 퍼즐 문제: 미로 찾기와 같은 퍼즐 문제를 해결하는 데 유용합니다.

DFS 소스코드 예제

# 그래프를 인접 리스트로 표현
graph = {
    'A': ['B', 'C'],
    'B': ['D', 'E'],
    'C': ['F'],
    'D': [],
    'E': ['F'],
    'F': []
}

def dfs_recursive(node, visited):
    if node not in visited:
        print(node, end=' ')
        visited.add(node)
        for neighbor in graph[node]:
            dfs_recursive(neighbor, visited)

# 사용 예시
visited = set()
# 또는
# visited = [False] * 7 로 구현할 수 있음.
# 그리고 숫자에 맞춰서 인덱스 0은 비워두는 게 편함.
print("재귀 DFS 탐색 결과:")
dfs_recursive('A', visited)  # 출력: A B D E F C

여기서 추가로 고려해야 할 점은,

• 인덱스 0 비워두면 편함.
• stack으로도 구현할 수 있음.

DFS의 시간 복잡도

DFS 알고리즘은 모든 정점과 간선을 한 번씩만 방문하는 특성을 가짐.

• 정점(V): 모든 정점을 한 번씩 방문하므로, 정점의 개수(V)만큼의 시간이 소요됨.

• 간선(E): 각 정점의 이웃 노드를 탐색하기 위해 모든 간선을 한 번씩 확인해야 함. 따라서 간선의 개수(E)만큼의 시간이 추가로 소요.

이 두 가지 작업을 합치면 V + E가 되고, 따라서 시간 복잡도는 O(V+E)임.