DFS(Depth-First Search)

DFS는 깊이 우선 탐색으로 그래프에서 깊은 부분을 우선으로 탐색하는 알고리즘이다.

먼저 그래프의 구조를 설명하면 그래프는 노드(정점)와 간선으로 표현되는데 위의 그림에서 원형 = '노드' , 간선 = '노드와 노드가 연결된 선'으로 보면 된다.

위의 그림을 보면 1번 부터 탐색해서 2번 -> 3번 -> 4번 까지 탐색을 진행한 후 5번 -> 6번 -> 7번 -> 8번 ... 이렇게 진행 하는것을 볼 수 있다.

DFS 탐색 과정

DFS의 탐색 과정은 다음과 같다.

1.시작 노드를 스택에 삽입 후 방문 처리함
2.1번에서 탐색 했던 노드의 인접 노드가 있으면 그 인접 노드를 스택에 넣고 방문 처리 한다. 만약 방문 하지 않은 인접 노드가 없다면 스택에 담긴 노드를 꺼낸다.
3.2번 과정을 더 이상 실행할 수 없을 때까지 진행한다.

DFS를 언제 사용해야 할까?

DFS는 경로의 특징을 저장할 수 있으므로 주로 특정 경로를 찾아야할 때 사용한다.

DFS 예제

해당 그림을 코드로 표현 해보면 다음과 같다.

def dfs(graph, v , visited):
    visited[v] = True   # 1번 부터 방문
    print(v , end=' ')
    for i in graph[v]:  # 1번과 연결된 2,3,8을 차례대로 순회
        if not visited[i]:  # 2번에 방문을 하지 않았다면 재귀 함수를 이용해 2번 방문을 완료 하고 2번과 연결된 노드를 순휘한다.
            dfs(graph, i, visited)


visited = [False] * 6
graph = [
    [],
    [2,3,4],
    [1,5],
    [1,4],
    [1,3],
    [2]
]
dfs(graph,1,visited)

참고 자료 :
<이것이 코딩 테스트다> - 나동빈
https://coding-archive31.tistory.com/24
https://kingpodo.tistory.com/47