반응형
탐색 알고리즘 DFS, BFS
DFS(Depth-First Search)
- 깊이 우선 탐색이라고 부르며, 그래프에서 깊은 부분을 우선적으로 탐색하는 알고리즘
- 시간복잡도는 O(N)
그래프는 Node와 Edge로 표현
그래프 탐색이란 하나의 노드를 시작으로 다수의 노드를 방문하는 것
프로그래밍에서는 그래프를 인접행렬이나 인접리스트로 표현할 수 있음
인접행렬 방식
- 2차원 배열에 각 노드가 연결된 형태를 기록하는 방식
- 연결되어 있지 않은 노드끼리는 무한의 비용이라고 작성
INF = 99999999
graph = [
[0, 7, 5],
[7, 0, INF],
[5, INF, 0]
]인접리스트 방식
- 모든 노드에 연결된 노드에 대한 정보를 차례대로 연결하여 저장
- 연결 리스트라는 자료구조 이용
graph = [[] for _ in range(3)]
graph[0].append((1, 7))
graph[0].append((2, 5))
graph[1].append((0, 7)
graph[2].append((0, 5))
print(graph)두 방식의 차이
- 인접행렬 방식은 노드 개수가 많을 수록 메모리가 불필요하게 낭비 됨
- 인접리스트 방식은 연결된 정보만을 저장하기 때문에 메모리 효율적 사용
DFS 동작 과정
- 탐색 시작 노드를 스택에 삽입 & 방문 처리
- 스택의 최상단 노드에 방문하지 않은 인접 노드가 있으면, 그 인접 노드를 스택에 삽입 & 방문 처리. 방문하지 않은 인접 노드가 없으면 스택에서 최상단 노드를 꺼냄
- 2번의 과정을 더 이상 수행할 수 없을 때 까지 반복
DFS 예제 (스택이 아닌 재귀함수로 구현)
BFS(Breadth First Search)
- 너비 우선 탐색
- 가까운 노드부터 탐색하는 알고리즘 (DFS는 최대한 멀리 있는 노드를 우선으로 탐색하는 방식)
- DFS는 스택, BFS는 큐 자료구조 이용
- 시간복잡도 O(N)
- 파이썬의 deque 라이브러리를 사용하는 것이 좋음
- 일반적으로 실제 수행시간은 DFS보다 좋은 편
BFS 동작 방식
- 탐색 시작 노드를 큐에 삽입하고 방문 처리
- 큐에서 노드를 꺼내 해당 노드의 인접 노드 중에서 방문하지 않은 노드를 모두 큐에 삽입하고 방문 처리
- 2번의 과정을 더 이상 수행할 수 없을 때 까지 반복
BFS 예제
DFS, BFS 동작 방식 차이
<Reference>
반응형