Depth First Search 깊이 우선 탐색 알고리즘

어떤 노드에서 다른 연관있는 노드로 이동하고
이동해서 도착한 노드에서 그 노드와 연관된 노드로 이동하고 ....

꼬리 물기 식으로 어떠한 관계가 있는 노드로 끝까지 물고 늘어지는 탐색 알고리즘이라고 나는 이해했다.

 

 

DFS 알고리즘이 이용하는 자료구조는 STACK

stack의 용도는 되돌아가기 위해서이다. (돌아갈까바그래~) 깊이 탐색하기 위해서 낮은애들부터 정복할 건데 다 정복하면 다시 위로 올라와서 정복하지 않은 아이들을 정복해 나가야 한다.

 

2번 노드에서 DFS를 시작한다고 가정한다면 

(여러개가 이어져 있다면 노드 번호가 가장 낮은 것부터 탐색 한다)

1번을 stack에 Push -> 3번을 stack에 Push -> 2번은 방문했으니 3번을 pop 하고 -> 되돌아와서 다시 1번이랑 연결되어 있는 4번을 stack에 Push 하면서 정복해나간다.

 

방문의 여부를 표시하는 visted 배열

한 놈씩 정복 할 때, 이전에 정복했던 녀석들은 재방문 할 필요가 없다

위에서 3번 노드를 방문했을 때, 2번은 시작점이자 방문한 놈이었기 때문에 더이상 갈데가 없다! -> 되돌아가자! 가 된것이다.

따라서 각 노드들이 방문했는지 여부를 표시한 visited 배열이 필요하다

 

 

DFS 알고리즘은 두가지 방식으로 구성할 수 있다. 

• Stack 자료구조를 이용한 방식
• Recursion 재귀를 이용한 방식

Recursion (재귀)를 이용한 방식

여러개의 도시가 있는 graph를 생각하고 모두 선으로 연결이 되어있다면 

간단한 재귀를 이용한 DFS 코드는 아래와 같이 생각할 수 있다

graph = [
    [],
    [4, 3, 2],
    [2, 4],
    [1, 3, ],
    [3, 5],
    [3, 4],
]

visited = [False]*9

result = []

def dfs(node, graph, visited):
    visited[node] = True

    result.append(node)

    for n in graph[node]:
        if visited[n] == False:
            dfs(n, graph, visited)


dfs(1, graph, visited)
print(result)

방문을 하자마자 visited를 True로 설정하고 

인접한 녀석들을 돌면서 visited 가 False인 경우만 꼬리를 물면서 탐색하는 방식이다.

여기서의 for 반복문이 자료구조 Stack 역할을 대신해준다. 되돌아 갈 수 있게 해준다

 

돌면서 result를 저장하고 있고,  recursion의 탈출은 연결되어있는 모든 노드들을 탐색하면 알아서 탈출하므로 탈출을 위한 조건문은 필요가 없다

 

시간 복잡도

O(N) : 각각의 노드를 한번씩 돌면서 재귀를 실행하고 있다.