[DFS 알고리즘][파이썬]-16일차

1. DFS 알고리즘의 정의

 

Depth-First Search, 깊이 우선 탐색.

탐색 하는 기준은 깊이가 우선이 된다

DFS를 공부할 때 자주 보게 되는 그림인데, 숫자가 써져있는 동그라미 자체를 'node' 라고 한다.

이 알고리즘을 이해하려면, 스택,큐, 재귀함수의 개념들에 대해서는 미리 공부를 해두어야 한다.

 

2. DFS 알고리즘의 로직

 

이 알고리즘은 무조건 깊게 들어간다. 계속 깊게 들어가고 갈 곳이 없으면 한 칸 위로 올라와서 더 깊게 갈 길이 있나? 하고 찾고, 있으면 그 길을 또 쭉 깊게 간다. 만약 없다면, 또 한 칸을 위로 올라가서 같은 로직을 반복한다.

이 코드를 말로 표현해보자.

1. 28번에서 dfs 코드를 실행

2. visited[1]=True 가 된다

3. print(1) end=' '라서 뒤의 print 문이 나올 때 까지 대기

4.for i in graph[1]:

    graph[1]=graph라는 2차원 리스트의 1번 인덱스, [2,3]

    i=2

    if not visitied[2]: 2번 노드가 방문되지 않았으면?

        dfs(graph,2,visited) 를 실행

    point: 3은 아직 실행이 안되었다!

 

5. visited[2]=True

6. print(2) end=' '라서 뒤의 print 문이 나올 때 까지 대기

7. for i in graph[2]:

    graph[2]=[1,8]

    1은 방문되었음으로 if 문에 안걸리고 8로 바로 직진

    dfs(graph,8,visited 실행)

 

......

-> dfs(graph,6,visited) -> [7,8] 이라서 8은 이미 방문되었으니까

-> dfs(graph,7,visited) -> [6,8]이라 패스

 

이제 처음에 시작되었던 for i in [2,3] 에서 3으로 가는것

이 로직이 쭉 반복

 

output: 1,2,8,6,7,3,4,5

    

 

예제로 dfs 활용은 다음 포스팅에서 다루겠다!