[python] 알고리즘 - 깊이 우선 탐색 / DFS(Depth First Search)

깊이 우선 탐색(DFS)

(레이아웃이 PC 에 최적화 되어있습니다.)

출처: https://practice.geeksforgeeks.org/problems/difference-between-bfs-abd-dfs

 

깊이 우선 탐색 알고리즘은 말 그대로  깊이를 우선순위로 두고 탐색한다. 위 이미지에서 우측의 DFS 알고리즘은 0 → 1 → 3 → 4 → 2 → 5 → 6 순서로 탐색을 한다. (이때 0에서 1, 2로 가는 순서는 상관 없다. 따라서 0 → 2 → 6 → 5 → 1 → 4 → 3으로도 탐색할 수 있다.)

 

 

위 그래프 구조를 파이썬 딕셔너리 형태로 표현하면 아래와 같다.

 

graph = dict()

graph[0] = [1, 2]

graph[1] = [0, 3, 4]

graph[2] = [0, 5, 6]

graph[3] = [1]

graph[4] = [1]

graph[5] = [2]

graph[6] = [2]

 

 

 

0에서 1로 움직이고 1에서는 3, 4를 순서대로 탐색한다. 이때 DFS 알고리즘은 큐와 스택을 활용한다.  res 리스트는 최종 결과로 반환할 리스트이고 visit은 탐색을 거쳐야할 리스트다.

 

 

시작점에 위치한 0이 res 리스트에 들어가고 0에서 탐색 가능한 1, 2가 visit 리스트에 추가된다. 

 

 

 

이제 visit 리스트의 가장 후미에 있는 2부터 탐색한다. 따라서 res에 2를 추가하고, 2에서 탐색할 수 있는 모든 노드를 추가한다. 

 

 

 

가장 후미에 위치한 6이 res에 추가된다. 그리고 6에서 탐색 가능한 모든 노드가 visit에 추가된다. 이때 2는 이미 res에 존재하므로 무시하고 바로 다음 노드인 5를 res에추가한다.

 

 

5에서 탐색 가능한 노드 2가 추가된다. 이때 visit의 2, 0은 이미 res에 존재하므로 무시하고 1이 추가된다. 다시 1에서 탐색 가능한 모든 노드가 visit에 추가된다.  이렇게 visit에 남은 데이터가 없을 때까지 반복한다.

 

 

 

 

아래 코드에서 1번 노드부터 탐색하고 싶다면 인풋 데이터를 뒤집거나 visit에 탐색 가능한 데이터를 리스트로 추가할때 뒤집어서 추가하는 방법도 가능할 것 같다.

#DFS
def dfs(graph, start):
    result, visit = [], []
    visit.append(start)
    
    while visit:
        node = visit.pop()
        if node not in result:
            result.append(node)
            visit.extend(graph[node])
    
    return result       


#Test Code
graph = dict()
graph[0] = [1, 2]
graph[1] = [0, 3, 4]
graph[2] = [0, 5, 6]
graph[3] = [1]
graph[4] = [1]
graph[5] = [2]
graph[6] = [2]

dfs(graph, 0)