[알고리즘] 깊이 우선 탐색 (DFS, Depth-First Search)이란?

깊이 우선 탐색(DFS, Depth-First Search)

- 그래프 탐색에서 루트 노드에서 시작해 다음 분기로 넘어가기 전에 해당 분기를 완벽하게 탐색하는 방법

- 재귀 혹은 스택 자료구조를 이용함

깊이우선탐색(DFS) : 위키백과

 

장점

- 현 경로상의 노드들만 기억하면 되므로 저장공간의 수요가 비교적 적다.

- 목표노드가 깊은 단계에 있을 경우 해를 빨리 구할 수 있다.

단점

- 해가 없는 경로에 깊이 빠질 가능성이 있다. 따라서 실제의 경우 미리 지정한 임의의  깊이까지만 탐색하고 목표노드를 발견하지 못하면 다음의 경로를 따라 탐색하는 방법이 유용할 수 있다.

- 얻어진 해가 최단 경로가 된다는 보장이 없다.

 

 

구현 예시(Python)

# DFS 메서드 정의
def dfs(graph, v, visited):
    # 현재 노드를 방문 처리
    visited[v] = True
    print(v, end=' ')
    # 현재 노드와 연결된 다른 노드를 재귀적으로 방문
    for i in graph[v]:
        if not visited[i]:
            dfs(graph, i, visited)

# 각 노드가 연결된 정보를 표현 (2차원 리스트)
graph = [
    [],
    [2, 3, 8],
    [1, 7],
    [1, 4, 5],
    [3, 5],
    [3, 4],
    [7],
    [2, 6, 8],
    [1, 7]
]

# 각 노드가 방문된 정보를 표현 (1차원 리스트)
visited = [False] * 9

# 정의된 DFS 함수 호출
dfs(graph, 1, visited)

-> 출력 결과 : 1 2 7 6 3 8 4 5

구현 참고 영상 : https://www.youtube.com/watch?v=7C9RgOcvkvo&t=2602s (나동빈님 강의 유튜브)