🌳깊이우선탐색(DFS, Depth-Fist Search)🌳
- 최대한 깊이 내려간 뒤, 더 이상 깊이 갈 곳이 없을 경우 옆으로 이동
- 루트 노드에서 시작해 다음 분기로 넘어가기 전에 해당 분기를 완벽하게 탐색하는 방식
- 정점의 자식들을 먼저 탐색하는 방식
1. DFS 방식 이해를 위한 예제
- 탐색 순서: A → B → D → E → F → C → G → H → I → J
- 루트 노드에서 시작해 다음 분기로 넘어가기 전에 해당 분기를 완벽하게 탐색하는 방식
2. 파이썬으로 그래프를 표현하는 방법
- 딕셔너리와 리스트 자료구조를 활용하여 그래프를 표현할 수 있음
graph = dict()
graph['A'] = ['B', 'C']
graph['B'] = ['A', 'D']
graph['C'] = ['A', 'G', 'H', 'I']
graph['D'] = ['B', 'E', 'F']
graph['E'] = ['D']
graph['F'] = ['D']
graph['G'] = ['C']
graph['H'] = ['C']
graph['I'] = ['C', 'J']
graph['J'] = ['I']
graph
''' output
{'A': ['B', 'C'],
'B': ['A', 'D'],
'C': ['A', 'G', 'H', 'I'],
'D': ['B', 'E', 'F'],
'E': ['D'],
'F': ['D'],
'G': ['C'],
'H': ['C'],
'I': ['C', 'J'],
'J': ['I']}
'''
3. DFS 알고리즘 구현
- 자료구조 스택과 큐를 활용
- 큐와 스택 구현은 별도 라이브러리를 활용할 수 있지만, 간단히 파이썬 리스트를 활용할 수 있음
- need_visit 스택과 visited 큐, 2개의 자료 구조를 생성
- DFS는 스택과 큐를 활용하고, BFS는 2개의 큐를 활용함
- 아래 코드는 오른쪽 방향으로 탐색하는 방식으로 구현함
- 오른쪽이든 왼쪽이든 방향은 정하기 나름이고, 탐색 방식만 같다면 DFS라고 볼 수 있음
def dfs(graph, start_node):
visited, need_visit = list(), list()
need_visit.append(start_node)
while need_visit:
node = need_visit.pop()
if node not in visited:
visited.append(node)
need_visit.extend(graph[node])
return visited
dfs(graph, 'A')
# ['A', 'C', 'I', 'J', 'H', 'G', 'B', 'D', 'F', 'E']
4. 시간 복잡도
- 일반적인 DFS 시간 복잡도
- 노드 수 : V
- 간선 : E
- 위 코드에서 while need_visit는 V + E번 수행
- 시간 복잡도 : O(V + E)
def dfs(graph, start_node):
visited, need_visit = list(), list()
need_visit.append(start_node)
count = 0
while need_visit:
count += 1
node = need_visit.pop()
if node not in visited:
visited.append(node)
need_visit.extend(graph[node])
print(count)
return visited
dfs(graph, 'A')
# 19
# ['A', 'C', 'I', 'J', 'H', 'G', 'B', 'D', 'F', 'E']
🪵너비우선탐색(BFS, Breadth-First Search)🪵
- 정점들과 같은 레벨에 있는 노드들(형제 노드들)을 먼저 탐색하는 방식
1. BFS 방식 이해를 위한 예제
- 탐색 순서 : A → B → C → D → G → H → I → E → F → J
- 루트노드에서 시작해서 인접한 노드를 먼저 탐색하는 방법으로, 시작정점으로부터 가까운 정점을 먼저 방문하고 멀리 떨어져 있는 정점을 나중에 방문하는 순회 방법
- 주로 두 노드 사이의 최단 경로를 찾고 싶을 때 이 방법을 선택
2. 파이썬으로 그래프를 표현하는 방법
- 딕셔너리와 리스트 자료구조를 활용하여 그래프를 표현할 수 있음
graph = dict()
graph['A'] = ['B', 'C']
graph['B'] = ['A', 'D']
graph['C'] = ['A', 'G', 'H', 'I']
graph['D'] = ['B', 'E', 'F']
graph['E'] = ['D']
graph['F'] = ['D']
graph['G'] = ['C']
graph['H'] = ['C']
graph['I'] = ['C', 'J']
graph['J'] = ['I']
graph
''' output
{'A': ['B', 'C'],
'B': ['A', 'D'],
'C': ['A', 'G', 'H', 'I'],
'D': ['B', 'E', 'F'],
'E': ['D'],
'F': ['D'],
'G': ['C'],
'H': ['C'],
'I': ['C', 'J'],
'J': ['I']}
'''
3. BFS 알고리즘 구현
- 자료구조 큐를 활용
- need_visit 큐와 visited 큐, 2개의 큐를 생성
- 큐의 구현은 간단히 파이썬 리스트를 활용
data = [1, 2, 3]
data.extend([4, 5])
data
# [1, 2, 3, 4, 5]
def bfs(graph, start_node):
visited = list()
need_visit = list()
need_visit.append(start_node)
while need_visit:
node = need_visit.pop(0)
if node not in visited:
visited.append(node)
need_visit.extend(graph[node])
return visited
bfs(graph, 'A')
# ['A', 'B', 'C', 'D', 'G', 'H', 'I', 'E', 'F', 'J']
4. 시간 복잡도
- 일반적인 BFS 시간 복잡도
- 노드 수 : V
- 간선 : E
- 위 코드에서 while need_visit는 V + E번 수행
- 시간 복잡도 : O(V + E)
def bfs(graph, start_node):
visited = list()
need_visit = list()
need_visit.append(start_node)
count = 0
while need_visit:
count += 1
node = need_visit.pop(0)
if node not in visited:
visited.append(node)
need_visit.extend(graph[node])
print(count)
return visited
bfs(graph, 'A')
# 19
# ['A', 'B', 'C', 'D', 'G', 'H', 'I', 'E', 'F', 'J']
🧩 깊이우선탐색(BFS) vs 너비우선탐색(DFS) 비교
| DFS(깊이우선탐색) | BFS(너비우선탐색) |
| 현재 정점에서 갈 수 있는 점들까지 들어가면서 탐색 | 현재 정점에 연결된 가까운 점들부터 탐색 |
| 스택 또는 재귀함수로 구현 | 큐를 이용해서 구현 |
✓시간복잡도
두 방식 모두 조건 내의 모든 노드를 검색한다는 점에서 시간 복잡도는 동일하다.
DFS와 BFS 둘 다 다음 노드가 방문하였는지를 확인하는 시간과 각 노드를 방문하는 시간을 합하면 된다.
'알고리즘 문제' 카테고리의 다른 글
| [Python]1012번.유기농 배추(그래프이론, 그래프 탐색, BFS, DFS) (1) | 2023.12.15 |
|---|---|
| [Python]1260번.DFS와 BFS(그래프이론, 그래프 탐색, BFS, DFS) (0) | 2023.12.13 |
| [Python]11286번.절댓값 힙(자료구조, 우선순위 큐) (0) | 2023.12.10 |
| [Python]2841번.외계인의 기타 연주(자료구조, 스택) (0) | 2023.12.10 |
| [Python]11057번.오르막 수(DP) (1) | 2023.12.07 |