DFS(Depth First Search)
출처:https://siloam72761.tistory.com/entry/파이썬-알고리즘-쉽게-이해하는-DFS-알고리즘-정의-특징-코드
-
깊이 우선 탐색이라고도 부르며 그래프에서 깊은 부분을 우선적으로 탐색하는 알고리즘이다.
-
그래프는 노드(Node)와 간선으로 표현된다. 노드는 정점(Vertex)이라고도 불린다.
-
그래프는 크게 2가지 방식으로 표현된다.
-
인접 행렬(Adjacency Martix)
2차원 배열에 각 노드가 연결된 형태를 기록하는 방식이다.INF = 99999999999 # 무한 설정 graph = [ [0, 7, 5], [7, 0, INF], [5, INF, 0] ] print(graph) # [[0, 7, 5], [7, 0, 999999999], [5, 999999999, 0]]
-
인접 리스트(Adjacency List)
모든 노드에 연결된 노드에 대한 정보를 차례대로 연결하여 저장# 행(Row)이 3개인 2차원 리스트로 인접 리스트 표현 graph = [[] for _ in range(3)] # 노드 0에 연결된 노드 정보 저장(노드, 거리) graph[0].append((1, 7)) graph[0].append((2, 5)) # 노드 1에 연결된 노드 정보 저장(노드, 거리) graph[1].append((0, 7)) # 노드 2에 연결된 노드 정보 저장(노드, 거리) graph[2].append((0, 5)) print(graph) # [[(1, 7), (2, 5)], [(0, 7)], [(0, 5)]]
-
-
인접 행렬 방식은 모든 관계를 저장하므로 노드 개수가 많을수록 메모리가 불필요하게 낭비된다.
-
인접 리스트 방식은 연결된 정보만을 저장하기 때문에 메모리를 효율적으로 사용한다.
-
하지만, 인접 리스트 방식은 인접 행렬 방식에 비해 노드 간 연결 정보를 얻는 속도가 느리다.
-
특정 노드와 연결된 모든 인접 노드를 순회해야 하는 경우, 인접 리스트 방식이 인접 행렬 방식에 비해 메모리의 공간 낭비가 적다.
-
DFS 동작 과정
출처: https://siloam72761.tistory.com/entry/파이썬-알고리즘-쉽게-이해하는-DFS-알고리즘-정의-특징-코드
cf. 번호가 낮은 순서부터 처리하도록 명시하는 경우가 일반적이다.
-
탐색 시작 노드를 스택에 삽입하고 방문 처리를 한다.
-
스택의 최상단 노드에 방문하지 않은 인접 노드가 있으면 그 인접 노드를 스택에 넣고 방문 처리를 한다. 방문하지 않은 인접 노드가 없으면 스택에서 최상단 노드를 꺼낸다.
-
2번의 과정을 더 이상 수행할 수 없을 때까지 반복한다.
노드 탐색 순서: 1 -> 3 -> 5 -> 7 -> 2 -> 4 -> 6
cf. 실제로는 스택을 사용하지 않아도 되며 탐색을 수행하는 것에 있어 데이터의 개수가 N개인 경우 O(N)의 시간이 소요된다.
구현
# 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 = [
[], # 0번 노드 (사용되지 않음)
[2, 3, 8], # 1번 노드와 연결된 노드들
[1, 7], # 2번 노드와 연결된 노드들
[1, 4, 5], # 3번 노드와 연결된 노드들
[3, 5], # 4번 노드와 연결된 노드들
[3, 4], # 5번 노드와 연결된 노드들
[7], # 6번 노드와 연결된 노드들
[2, 6, 8], # 7번 노드와 연결된 노드들
[1, 7] # 8번 노드와 연결된 노드들
]
# 각 노드가 방문된 정보를 리스트 자료형으로 표현 (1차원 리스트)
visited = [False] * 9
# 정의된 DFS 함수 호출
dfs(graph, 1, visited)
# 출력
1 2 7 6 8 3 4 5BFS(Breadth First Search)
출처: https://www.linkedin.com/pulse/breadth-first-search-vishnu-vardhini/
-
너비 우선 탐색이라고도 불리며, 가까운 노드부터 탐색하는 알고리즘이다.
-
DFS와 달리 최대한 가까이 있는 노드부터 탐색 한다.
-
선입 선출 방식인 큐(deque)를 이용한다.
-
O(N)의 시간이 소요된다.
-
DFS보다 실제 수행 시간이 조금 더 짧다.
BFS 동작 과정
출처: -
탐색 시작 노드를 큐에 삽입하고 방문 처리를 한다.
-
큐에서 노드를 꺼내 해당 노드의 인접 노드 중에서 방문하지 않은 노드를 모두 큐에 삽입하고 방문 처리를 한다.
-
2번의 과정을 더 이상 수행할 수 없을 때까지 반복한다.
노드 탐색 순서: 1 -> 2 -> 3 -> 8 -> 4 -> 5 -> 6 -> 7
구현
from collections import deque
# BFS 메서드 정의
def bfs(graph, start, visited):
# Queue 구현을 위해 deque 라이브러리 사용
queue = deque([start])
# 현재 노드를 방문 처리
visited[start] = True
# 큐가 빌 때까지 반복
while queue:
# 큐에서 하나의 원소를 뽑아 출력
v = queue.popleft()
print(v, end=' ')
# 해당 원소와 연결된, 아직 방문하지 않은 원소들을 큐에 삽입
for i in graph[v]:
if not visited[i]:
queue.append(i)
visited[i] = True
# 각 노드가 연결된 정보를 리스트 자료형으로 표현 (2차원 리스트)
graph = [
[], # 0번 노드 (사용되지 않음)
[2, 3, 8], # 1번 노드와 연결된 노드들
[1, 7], # 2번 노드와 연결된 노드들
[1, 4, 5], # 3번 노드와 연결된 노드들
[3, 5], # 4번 노드와 연결된 노드들
[3, 4], # 5번 노드와 연결된 노드들
[7], # 6번 노드와 연결된 노드들
[2, 6, 8], # 7번 노드와 연결된 노드들
[1, 7] # 8번 노드와 연결된 노드들
]
# 각 노드가 방문된 정보를 리스트 자료형으로 표현 (1차원 리스트)
visited = [False] * 9
# 정의된 BFS 함수 호출
bfs(graph, 1, visited)
# 출력
1 2 3 8 7 4 5 6DFS VS BFS
| 구분 | DFS (Depth First Search) | BFS (Breadth First Search) |
|---|---|---|
| 탐색 방식 | 한 경로를 끝까지 탐색 후 백트래킹 | 현재 노드와 인접한 노드부터 탐색 |
| 구현 방법 | 재귀(스택) 또는 명시적 스택 사용 | 큐 사용 |
| 자료구조 | 스택 (재귀 호출 스택 포함) | 큐 (FIFO) |
| 동작 원리 | LIFO (Last In, First Out) | FIFO (First In, First Out) |
| 방문 순서 | 깊이 우선 (먼저 깊은 곳으로 이동) | 너비 우선 (먼저 가까운 곳으로 이동) |
| 메모리 사용량 | 비교적 적음 | 비교적 많음 |
| 적용 사례 | 경로 찾기, 미로 탐색, 백트래킹 문제 | 최단 경로 탐색, 레벨별 탐색 |
| 장점 | 구현이 간단하고 메모리 효율적 | 최단 경로를 보장 |
| 단점 | 최단 경로를 보장하지 않음 | 메모리 사용량이 많음 |
| 종료 조건 | 재귀 호출이 종료되거나 스택이 빌 때까지 | 큐가 빌 때까지 |
| 탐색 대상 | 깊은 경로 우선 | 인접한 경로 우선 |
cf. 1차원 배열이나 2차원 배열을 그래프 형태로 생각하면 문제를 쉽게 풀 수 있다. 탐색 문제를 보면 그래프 형태로 표현하여 풀 수 있도록 하자.
해당 글은 다음 도서의 내용을 정리하고 참고한 글임을 밝힙니다. 보다 자세한 내용은 아래 책에서 확인할 수 있습니다. 나동빈, ⌜이것이 취업을 위한 코딩 테스트다 with 파이썬⌟, 한빛미디어, 2020, 604쪽
