DFS 알고리즘 (graph_탐색)

DFS 알고리즘

DFS - 한 놈(?)씩 먼저 팬다

-  DFS는 그래프(정점의 수: N, 간선의 수: E)의 모든 간선을 조회한다.
-   인접 리스트로 표현된 그래프: O(N+E)
-   인접 행렬로 표현된 그래프: O(N^2)
-   즉, 그래프 내에 적은 숫자의 간선만을 가지는 희소 그래프(Sparse Graph) 의 경우 인접 행렬보다 인접 리스트를 사용하는 것이 유리하다.

search_object = 7 + 1  #개체의 수(vertex) + 0번 개체(임의)

graph = [
    [], # 노드 탐색은 1번부터 하므로, 0번에는 빈 리스트를 입력
    [2,3],     #1번과 연결된 개체
    [1,4,5],       #2번과 연결된 개체
    [1,4,6],     #3번과 연결된 개체
    [2,3,5,7],       #4번과 연결된 개체
    [2,4,7],       #5번과 연결된 개체
    [3,7],         #6번과 연결된 개체
    [4,5,6]    #7번과 연결된 개체

]
visited = [False]*search_object #방문 이력 리스트

def dfs(graph,v,visited):
    visited[v] = True #탐색 후 탐색 결과를 저장
    print(v, end=" ") # 탐색 경로를 출력
    for i in graph[v]: #연결된 노드중에서
        if not visited[i]:  # 해당 노드가 not(False) + False(방문하지 않은 노드라면) = True
            dfs(graph, i, visited) #그 노드를 기준으로 재귀적으로 방문하도록 설정

print(dfs(graph,1,visited))




#DFS탐색기법은 stack 구조와 같다

코딩테스트에서 기본이지만 가장 직관적으로 이해하기 어려운(재귀함수..) DFS 알고리즘이다.