[Python] 깊이 우선 탐색 DFS

깊이 우선 탐색

시작 정점의 한 방향으로 갈 수 있는 경로가 있는 곳까지 깊이 탐색하다가 갈 수 있는 곳이 없으면, 가장 마지막에 만났던 갈림길 간선이 있는 정점으로 돌아와 다른 방향의 정점으로 탐색을 계속 반복하여 모든 정점을 방문하는 방법

1. 루트 노드를 스택에 넣고 방문처리 한다.
2. 스택 최상단 노드의 인접 노드 중 방문하지 않은 노드 하나를 스택에 넣고 방문처리한다. 만약 인접 노드를 모두 방문한 경우 스택을 Pop 한다.
3. 2단계를 더 이상 수행할 수 없을 때 까지 (스택이 빌 때 까지) 반복한다.

💡 특징

• 가장 마지막에 만났던 정점으로 돌아가 다시 탐색을 반복하므로 LIFO 구조의 스택 사용
• 넓게 탐색하기 전에 깊게 탐색하므로 깊이 우선 탐색(DFS)
• 깊이 우선 탐색(DFS)이 넓이 우선 탐색(BFS)보다 간단
• 탐색 속도는 DFS가 BFS보다 느림
• 스택과 재귀 알고리즘의 형태로 구현 가능
• 트리에서 사용되는 모든 순회는 DFS 의 종류

사용 예시

• 미로 탐색 문제 등의 알고리즘
• 경로의 특징을 저장해야하는 문제

def dfs(n): # dfs 정의
    visited[n] = True
    print(n, end=' ')
    for i in graph[n]:
        if not visited[i]:
            dfs(i)

graph = [[],[2,5,9],[3],[4],[],[6,8],[7],[],[],[10],[]] 
visited = [False] * len(graph) #방문 여부 처리
print(dfs(1))
#출력 : 1 2 3 4 5 6 7 8 9 10

출처
https://edder773.tistory.com/45
https://hudi.blog/dfs-bfs/