1. 서론
최근 많은 기업들이 알고리즘을 활용한 코딩 테스트를 진행하고 있습니다. 이러한 코딩 테스트에서는
DFS(깊이 우선 탐색)와 BFS(너비 우선 탐색)와 같은 그래프 탐색 알고리즘이 빈번하게 출제됩니다.
본 글에서는 DFS와 BFS의 기초 개념을 정리하고, 이를 바탕으로 한 알고리즘 문제 하나를 제시하여
문제 풀이 과정을 자세히 설명하겠습니다.
2. DFS와 BFS 개요
2.1 DFS (Depth-First Search)
DFS는 그래프의 한 정점에서 시작하여 가능한 멀리 있는 정점까지 탐색한 후, 더 이상 탐색할 정점이 없으면
마지막으로 방문한 정점으로 돌아와서 다시 탐색을 진행하는 방식입니다. 이때 스택 자료구조를 사용하거나,
재귀 함수를 이용하여 구현할 수 있습니다. DFS는 다음과 같은 과정을 거칩니다:
- 시작 정점을 스택에 추가하고 방문처리합니다.
- 스택의 꼭대기에서 정점을 하나 꺼내고, 해당 정점의 인접 정점 중 아직 방문하지 않은 정점을
스택에 추가합니다. - 모든 정점을 탐색할 때까지 위의 과정을 반복합니다.
2.2 BFS (Breadth-First Search)
BFS는 그래프의 한 정점에서 시작하여 인접한 모든 정점을 먼저 탐색한 후, 그 인접 정점에서 다시 인접한
정점을 탐색하는 방식입니다. 이때 큐 자료구조를 사용하여 구현됩니다. BFS의 과정은 다음과 같습니다:
- 시작 정점을 큐에 추가하고 방문 처리를 합니다.
- 큐에서 정점을 하나 꺼내고, 해당 정점의 인접 정점 중에서 아직 방문하지 않은 정점을 큐에
추가합니다. - 모든 정점을 탐색할 때까지 위의 과정을 반복합니다.
3. 알고리즘 문제 소개
문제: 경로 탐색하기
다음은 DFS와 BFS를 이용하여 경로를 탐색하는 문제입니다.
문제 설명: 주어진 그래프와 두 정점 A, B가 있을 때,
A에서 B로 가는 경로가 존재하는지 확인하시오.
그래프는 인접 리스트 형태로 주어집니다.
input:
graph = {
'A': ['B', 'C'],
'B': ['D'],
'C': ['D', 'E'],
'D': ['F'],
'E': [],
'F': []
}
start = 'A'
end = 'F'
output: True (A에서 F로 가는 경로가 존재)
4. 문제 풀이 과정
4.1 DFS로 경로 탐색하기
DFS를 사용하여 경로를 탐색하는 방법은 다음과 같습니다.
재귀 함수를 이용하여 구현할 수 있으며, 방문한 정점을 저장하기 위해 set 자료구조를 활용할 수 있습니다.
def dfs(graph, start, end, visited):
if start == end:
return True
visited.add(start)
for neighbor in graph[start]:
if neighbor not in visited:
if dfs(graph, neighbor, end, visited):
return True
return False
graph = {
'A': ['B', 'C'],
'B': ['D'],
'C': ['D', 'E'],
'D': ['F'],
'E': [],
'F': []
}
start = 'A'
end = 'F'
visited = set()
result = dfs(graph, start, end, visited)
위의 코드를 통해 DFS를 사용하여 경로 탐색을 할 수 있습니다.
처음에 시작 정점 A가 주어지면, 해당 정점의 방문 상태를 체크한 후 인접 정점으로
재귀 호출을 통해 탐색을 진행합니다.
정점 F에 도달했을 때 True를 반환하면 경로가 존재하는 것입니다.
4.2 BFS로 경로 탐색하기
BFS를 사용하여 경로를 탐색하는 방법은 큐를 사용하여 정점 방문 기록을 유지하는 것입니다.
from collections import deque
def bfs(graph, start, end):
queue = deque([start])
visited = set([start])
while queue:
vertex = queue.popleft()
if vertex == end:
return True
for neighbor in graph[vertex]:
if neighbor not in visited:
visited.add(neighbor)
queue.append(neighbor)
return False
graph = {
'A': ['B', 'C'],
'B': ['D'],
'C': ['D', 'E'],
'D': ['F'],
'E': [],
'F': []
}
start = 'A'
end = 'F'
result = bfs(graph, start, end)
BFS를 구현한 위의 코드와 같이 큐를 이용해 각 정점의 인접 정점을 하나씩
탐색해 나가면서 확인하면 A에서 F로 가는 경로가 있는지를 알 수 있습니다.
큐는 탐색하는 과정에서 사용되며, 방문한 정점도 기록합니다.
5. 결론
DFS와 BFS는 서로 다른 탐색 방법으로, 각각의 특성에 따라 다양한 문제에 적합합니다.
구조의 깊이를 우선적으로 탐색하고 싶은 경우에는 DFS가, 최단 거리 탐색을 원할 경우에는 BFS가
더 유리합니다. 본 글에서는 간단한 경로 탐색 문제를 통해 두 알고리즘의 구현과
그 과정에서의 차이를 보여드렸습니다. 이러한 기초를 바탕으로 더 복잡한 알고리즘 문제에
도전해 볼 수 있을 것입니다.
6. 참고 자료
- Data Structures and Algorithms in Python by Michael T. Goodrich
- Introduction to Algorithms by Thomas H. Cormen
- Python Documentation: https://docs.python.org/3/