[알고리즘] 깊이 우선 탐색(DFS) 알고리즘에 대해 알아보자!(+Python 구현)

본 포스팅에서는 깊이 우선 탐색 DFS(Depth-First Search) 알고리즘에 대해 알아봅니다.

📚 목차

1. DFS 알고리즘이란?
2. DFS 알고리즘 동작 과정
3. DFS 파이썬 구현

1. DFS 알고리즘이란?

DFS(Depth-First Search)는 그래프 전체를 탐색하는 방법(i.e., 완전 탐색) 중 하나로, '깊이'를 우선적으로 탐색하는 알고리즘입니다. DFS는 한 노드를 시작으로 다음 분기(branch)로 넘어가기 전에 해당 분기를 완벽하게 탐색합니다. 예를 들어, DFS 알고리즘은 미로 탐색 시 한 방향으로 모든 노드를 방문하다가 더 이상 다른 노드를 방문할 수 없는 노드에 이르렀을 때, 다시 가장 가까운 갈래길로 돌아가 방문하지 않은 노드 방향으로 탐색을 이어가는 방법입니다. 특히 그래프에서 간선이나 변수 정보를 수시로 변경해야 하는 문제는 DFS를 활용하는 것이 효과적입니다.

2. DFS 동작 과정

DFS 알고리즘의 동작 과정을 이해하기 위해서는 먼저 그래프 자료구조와 스택 자료구조를 먼저 이해하셔야 합니다. 관련한 내용은 아래 링크를 참고해 주세요.

[자료구조] 그래프 자료구조에 대해 알아보자!(노드, 간선, 루트 노드, 깊이, 높이, 차수)

[자료구조] 스택(Stack)에 대해 알아보자(+ Python)

DFS 알고리즘의 구체적인 동작 과정은 다음과 같습니다.

1️⃣ 탐색 시작 노드 정보를 스택에 삽입하고 *방문 처리합니다.
2️⃣ 스택 내 최상단 노드에 방문하지 않은 노드가 있다면 그 인접 노드 정보를 스택에 삽입하고 방문 처리합니다.
만일 방문하지 않은 인접 노드가 없다면 스택 내 최상단 노드를 꺼냅니다.
3️⃣ 2번의 과정을 더 이상 수행할 수 없을 때까지 반복합니다.

여기서 *방문 처리란 탐색한 노드를 재방문하지 않도록 구분하는 것입니다. 즉, 스택에 한 번이라도 삽입된 노드를 다시 삽입하지 않도록 체크하는 것이죠.

이제 아래 그림 1 과 같은 그래프 예시를 통해 DFS 동작 과정을 알아보겠습니다. 노드 1을 시작 노드로 설정하겠습니다. 일반적으로 인접한 노드가 2개 이상인 경우에는 해당 노드들 중 번호가 낮은 노드부터 처리합니다. 편의상 현재 처리 중인 스택 내 최상단 노드는 파란색으로,방문 처리한 노드는회색으로 표시하겠습니다.

그림 1. DFS 동작 설명을 위한 그래프 예시

(1) 시작 노드인 노드 1을 스택에 삽입하고 방문 처리합니다.

 

 

(2) 스택 내 최상단 노드인 노드 1에 인접한 노드는 2, 3이 있습니다. 번호가 낮은 노드 2를 스택에 삽입하고 방문 처리합니다.

 

 

(3) 스택 내 최상단 노드인 노드 2에 인접한 노드 8을 스택에 삽입하고 방문 처리합니다.

 

 

(4) 스택 내 최상단 노드인 노드 8에 인접한 노드는 6과 7이 있으며, 번호가 낮은 노드 6을 스택에 삽입하고 방문 처리합니다.

 

 

(5) 스택 내 최상단 노드인 노드 6에 인접하며 방문하지 않은 노드 7을 스택에 삽입하고 방문 처리합니다.

 

 

(6) 최상단 노드인 노드 7에 인접하며 방문하지 않은 노드가 없으므로 스택에서 노드 7을 꺼냅니다.

 

 

(7) 최상단 노드인 노드 6에 인접하며 방문하지 않은 노드가 없으므로 스택에서 노드 6을 꺼냅니다.

 

 

(7) 최상단 노드인 노드 8에도 인접하며 방문하지 않은 노드가 없으므로 스택에서 노드 8을 꺼냅니다.

 

 

(8) 최상단 노드인 노드 2에 인접하며 방문하지 않은 노드가 없으므로 스택에서 노드 2를 꺼냅니다.

 

 

(9) 노드 1에 인접하면서 방문 이력이 없는 노드 3을 스택에 삽입하고 방문 처리합니다.

 

 

(9) 노드 3에 인접하면서 방문하지 않은 노드는 노드 4와 5가 있지만, 번호가 낮은 노드 4를 스택에 삽입하고 방문 처리합니다.

 

 

(10) 노드 4에 인접한 노드 5를 스택에 넣고 방문 처리합니다.

 

 

(11) 이제 방문하지 않은 노드가 없기 때문에 스택에서 모든 노드를 차례대로 꺼냅니다.

 

결과적으로 노드의 탐색 순서, 즉 스택에 삽입한 순서는 다음과 같습니다.

1 -> 2 -> 8 -> 6 -> 7 -> 3 -> 4 -> 5

3. DFS 파이썬 구현

이제 앞서 살펴본 예시 그래프를 DFS 알고리즘을 통해 탐색하는 과정을 파이썬으로 구현해 봅니다. DFS는 스택 자료구조를 이용하는 알고리즘이므로 재귀 함수를 활용하면 간결하게 코드를 작성할 수 있습니다.

# DFS 메서드 정의
def dfs (graph, node, visited):
    # 해당 노드를 방문 처리
    visited[node] = True
    # 탐색 순서 출력
    print(node, end = ' ')
    # 한 노드로부터 인접한 다른 노드를 재귀적으로 방문 처리
    for i in graph[node]:
        if not (visited[i]):
            dfs (graph, i, visited)

위와 같이 DFS 메서드를 정의해 줍니다.

graph = [
    [],
    [2, 3],
    [1, 8],
    [1, 4, 5],
    [3, 5],
    [3, 4],
    [7, 8],
    [6, 8],
    [2, 6, 7]
]

노드 간의 연결 정보는 위와 같이 2차원 배열을 통해 표현할 수 있습니다. 즉, 리스트 내 인덱스는 노드 번호를 의미하고 각 인덱스에 해당하는 원소에 해당 노드에 인접한 노드 번호가 담겨 있습니다.

# 노드별로 방문 정보를 리스트로 표현
visited = [False] * 9

노드별로 방문 정보를 저장할 리스트를 초기화합니다.

잠깐, 왜 실제 그래프 내 노드 개수보다 2차원 배열에 원소 개수는 1개 더 많나요?

리스트 내 원소의 인덱스와 노드 번호를 일치시키기 위해, 인덱스 0에 빈 리스트를 넣어줌으로써 기존 그래프 내 노드 개수보다 방문 정보를 담은 리스트 내 원소 개수를 1개 더 많게 세팅하였습니다. 이처럼 인덱스와 노드 번호를 일치시켜 줌으로써 보다 직관적으로 노드 간의 연결 및 방문 정보를 파악할 수 있도록 세팅하였습니다.

# 정의한 DFS 메서드 호출(노드 1을 탐색 시작 노드로 설정)
dfs(graph, 1, visited)

DFS 메서드를 호출하면 탐색 순서가 차례로 출력되는 것을 확인하실 수 있습니다.

실행결과

1 2 6 8 6 7 3 4 5

전체 소스코드

# DFS 메서드 정의
def dfs (graph, node, visited):
    # 해당 노드를 방문 처리
    visited[node] = True
    # 탐색 순서 출력
    print(node, end = ' ')
    # 한 노드로부터 인접한 다른 노드를 재귀적으로 방문 처리
    for i in graph[node]:
        if not visited[i]:
            dfs(graph, i, visited)
            
graph = [
    [],
    [2, 3],
    [1, 8],
    [1, 4, 5],
    [3, 5],
    [3, 4],
    [7, 8],
    [6, 8],
    [2, 6, 7]
]

# 노드별로 방문 정보를 리스트로 표현
visited = [False] * 9

# 정의한 DFS 메서드 호출(노드 1을 탐색 시작 노드로 설정)
dfs(graph, 1, visited)

실행결과

1 2 6 8 6 7 3 4 5

📚 참고할 만한 포스팅

1. [알고리즘] 너비 우선 탐색(BFS) 알고리즘에 대해 알아보자!(+Python 구현)
2. [자료구조] 스택(Stack)에 대해 알아보자(+ Python)

---

오늘은 DFS 알고리즘에 대해 알아보았습니다.
포스팅 내용에 오류가 있을 경우 댓글 남겨주시면 감사드리겠습니다.
그럼 오늘도 즐거운 하루 보내시길 바랍니다 :)
고맙습니다.