Posted by 깊이 우선 탐색(DFS, Depth-First Search)은 그래프 또는 트리 자료 구조에서 널리 사용되는 탐색 알고리즘이다. DFS는 시작 노드에서 출발해 각 분기(Branch)를 가능한 깊이까지 탐색한 후, 다른 분기로 이동하는 방식으로 작동한다.
이번 포스트에서는 DFS의 이론적인 개념부터 자료 구조에 대한 설명, 그리고 Python으로 구현하는 방법까지 자세히 설명하고자 한다.
DFS의 이론적 배경
깊이 우선 탐색은 트리나 그래프 같은 구조에서 노드를 방문하는 방법 중 하나이다.
DFS는 탐색 시작점에서 출발하여 한 방향으로 깊이 탐색한 후, 더 이상 깊이 탐색할 수 없을 때 다음 분기로 이동하는 방식으로 이루어진다.
DFS는 스택(Stack)을 사용하여 구현할 수 있으며, 재귀(Recursion)를 사용해도 동일한 결과를 얻을 수 있다.
DFS의 주요 특징
- 방문 순서: DFS는 특정 경로를 따라 가능한 한 깊이 내려가면서 노드를 방문한다. 더 이상 방문할 노드가 없을 때는 이전 분기로 돌아와 다음 경로를 탐색한다.
- 완전성: DFS는 그래프가 유한한 경우 반드시 모든 노드를 방문한다.
- 비선형 구조 탐색: DFS는 트리뿐만 아니라 순환이 있는 그래프에서도 사용할 수 있다.
- 경로 탐색: DFS는 노드 간의 경로를 찾는 데 유용하며, 미로 탐색과 같은 문제에서도 효과적이다.
자료 구조
DFS를 구현하기 위해서는 다음과 같은 자료 구조를 이해해야 한다
그래프(Graph)
그래프는 노드(Node)와 그 노드를 연결하는 간선(Edge)으로 구성된다. DFS에서는 그래프를 탐색하면서 노드와 간선을 방문하게 되며, 그래프는 인접 리스트(Adjacency list)나 인접 행렬(Adjacency matrix)로 표현할 수 있다.
스택(Stack)
DFS는 기본적으로 스택을 사용하는 알고리즘이다. 스택은 LIFO(Last In, First Out) 구조로, 가장 마지막에 삽입된 요소가 먼저 제거된다. 스택을 사용하여 DFS의 탐색 순서를 관리할 수 있다.
방문 표시(Visited)
DFS에서는 이미 방문한 노드를 다시 방문하지 않도록 방문 여부를 기록하는 것이 중요하다. 이를 위해 방문한 노드를 기록하는 자료 구조(예: 집합(Set) 또는 리스트(List))를 사용한다.
DFS의 동작 과정
DFS는 다음과 같은 순서로 동작한다
- 시작 노드를 스택에 추가하고, 방문했다고 표시한다.
- 스택의 최상단 노드를 꺼내어 해당 노드를 방문한다.
- 현재 노드에서 갈 수 있는 모든 인접 노드를 스택에 추가한다(이미 방문한 노드는 제외).
- 스택이 비어있지 않은 한 이 과정을 반복한다.
DFS의 Python 구현
DFS를 Python으로 구현하는 방법을 살펴보자.
여기서는 재귀(Recursion)를 사용한 방법과 스택(Stack)을 사용한 반복적 방법 두 가지를 알아볼 예정이다.
재귀(Recursion)를 사용한 DFS 구현
# 그래프를 인접 리스트로 표현
graph = {
'A': ['B', 'C'],
'B': ['D', 'E'],
'C': ['F'],
'D': [],
'E': ['F'],
'F': []
}
# DFS 함수 (재귀적 구현)
def dfs_recursive(node, visited):
if node not in visited:
print(node, end=' ') # 방문한 노드를 출력
visited.add(node) # 노드를 방문한 것으로 표시
for neighbor in graph[node]: # 인접한 노드들을 순차적으로 방문
dfs_recursive(neighbor, visited)
# 방문 여부를 기록할 집합
visited = set()
# DFS 시작
dfs_recursive('A', visited)
코드 설명
graph: 그래프를 인접 리스트로 표현했다. 각 키는 노드를 나타내며, 해당 키의 값은 인접 노드 리스트이다.dfs_recursive함수: 이 함수는 재귀적으로 DFS를 수행한다. 현재 노드가 방문되지 않았다면 방문을 기록하고, 그 노드와 인접한 노드들을 재귀적으로 방문한다.visited: 방문한 노드를 기록하는 집합이다.
스택(Stack)을 사용한 DFS 구현
# 그래프를 인접 리스트로 표현
graph = {
'A': ['B', 'C'],
'B': ['D', 'E'],
'C': ['F'],
'D': [],
'E': ['F'],
'F': []
}
# DFS 함수 (스택을 사용한 반복적 구현)
def dfs_stack(start_node):
visited = set() # 방문한 노드를 기록할 집합
stack = [start_node] # 탐색 시작 노드를 스택에 추가
while stack:
node = stack.pop() # 스택에서 노드를 꺼냄
if node not in visited:
print(node, end=' ') # 방문한 노드를 출력
visited.add(node) # 노드를 방문한 것으로 표시
stack.extend(reversed(graph[node])) # 인접한 노드들을 스택에 추가 (역순으로 추가하여 올바른 순서로 탐색)
# DFS 시작
dfs_stack('A')
코드 설명
dfs_stack함수: 이 함수는 스택을 사용하여 DFS를 반복적으로 수행한다. 스택에서 노드를 꺼내 방문 여부를 확인하고, 방문하지 않은 경우 해당 노드를 방문 처리한 후 인접한 노드를 스택에 추가한다.stack: 탐색할 노드를 담는 스택이다. 여기서는 시작 노드를 먼저 추가한 후, 인접 노드를 역순으로 추가하여 올바른 순서로 탐색한다.
DFS의 활용 사례
DFS는 다음과 같은 다양한 문제에서 유용하게 사용될 수 있다
- 경로 탐색: 특정 노드에서 다른 노드까지의 경로를 찾는 문제.
- 미로 탐색: 미로에서 출구를 찾는 문제.
- 사이클 탐지: 그래프 내에서 사이클(순환)을 탐지하는 문제.
- 위상 정렬: 순서가 정해진 작업을 정렬하는 문제.
결론
이번 포스트에서는 깊이 우선 탐색(DFS)에 대해 이론적 배경부터 자료 구조, 그리고 Python으로 구현하는 방법까지 자세히 설명해 보았다. DFS는 트리나 그래프 구조에서 매우 중요한 탐색 방법 중 하나이며, 다양한 문제 해결에 활용될 수 있다. 제공된 예제 코드와 함께 DFS의 개념을 잘 이해하고, 이를 바탕으로 다양한 알고리즘 문제를 해결해 보시길 바란다.