- 탐색 알고리즘
- 많은 양의 데이터 중에서 원하는 데이터를 찾는 과정을 의미한다.
- DFS, BFS는 그래프 탐색 알고리즘에 속한다.
- 그래프
- 노드(Node)와 간선(Edge)으로 이루어진 자료구조의 일종
- 간선으로 연결되어 있는 노드들을 인접하다(adjacent)라고 표현된다.
- 구현하는 방식 → 인접 행렬, 인접 리스트
인접 리스트
graph = [
[1, 2, 3],
[0, 3],
[0, 3],
[0, 1, 2]
]- 각각의 인덱스에 해당하는 노드에 연결된 노드들을 리스트 형태로 저장하는 방식
- 연결 리스트를 활용하여 표현하는 방식
- 그래프 내에 적은 숫자의 간선만을 가지는 희소 그래프의 경우
인접 행렬
graph = [[0, 1, 1, 1],
[1, 0, 0, 1],
[1, 0, 0, 1],
[1, 1, 1, 0]]- 각 행과 열이 노드를 의미한다.
- 2차원 배열을 활용하여 그래프를 표현하는 방식
- 그래프에 간선이 많이 존재하는 밀집 그래프의 경우
인접 리스트 vs 인접 행렬
| 인접 리스트 | 인접 행렬 | |
| 장점 | - 연결된 것만 기록 - 인접한 노드들을 바로 알 수 있음 |
- 두 노드의 간선의 존재 여부를 바로 알 수 있음 |
| 단점 | - 두 노드가 연결되어 있는지 확인이 인접 행렬보다 느림 | - 모든 관계를 기록함으로 노드의 개수가 많을 수록 불필요한 메모리 낭비가 일어남 |
- DFS와 BFS
그래프 탐색
- 하나의 정점으로부터 시작 → 차례대로 모든 정점들을 한 번씩 방문하는 것
DFS
개념
- 깊이 우선 탐색
- 사용하는 경우: 모든 노드를 방문하고자 하는 경우에 택한다.
특징
- 자기 자신을 호출하는 순간 → 순환 알고리즘의 형태를 가지고 있다.
- 어떤 노드를 방문했었는지 여부를 반드시 검사해야 한다. → 검사하지 않을 경우 무한루프…
구현
- 재귀함수
- 스택
시간 복잡도
- 인접 리스트 : O(N + E)
- 인접 행렬 : O(N^2)
d_check = [False for _ in range(n+1)]
def dfs(x):
d_check[x] = True
print(x, end=' ')
for y in edge[x]:
if d_check[y] == False:
dfs(y)BFS
개념
- 너비 우선 탐색
- 사용하는 경우: 두 노드 사이에 최단 경로 or 임의의 경로를 찾고 싶을 때
특징
- 재귀적으로 동작하지 않는다.
- dfs와 마찬가지로 어떤 노드를 방문했었는지 여부를 반드시 검사해야 한다.
→ 검사하지 않을 경우 무한루프…
구현
- 큐(Queue) 이용
시간 복잡도
- 인접 리스트 : O(N + E)
- 인접 행렬 : O(N^2)
from collections import deque
def bfs():
queue = deque([start])
b_check = [False for _ in range(n+1)]
b_check[start] = True
while queue:
v = queue.popleft()
print(v, end= ' ')
for i in edge[v]:
if not b_check[i]:
b_check[i] = True
queue.append(i)DFS vs BFS
| DFS | BFS |
| 스택 or 재귀 함수 | 큐 |
| 최적 해라는 보장 X | 항상 최적 해임을 보장 |
| 그래프 규모가 클 때 | 그래프 규모가 작을 때 |
| 특정 목표 노드를 찾을 때 | 최단 경로를 찾을 때 |
공부하면서 풀기 좋은 백준 문제 추천해드립니다.
1260번: DFS와 BFS
첫째 줄에 정점의 개수 N(1 ≤ N ≤ 1,000), 간선의 개수 M(1 ≤ M ≤ 10,000), 탐색을 시작할 정점의 번호 V가 주어진다. 다음 M개의 줄에는 간선이 연결하는 두 정점의 번호가 주어진다. 어떤 두 정점 사
www.acmicpc.net
더보기를 누르시면 제가 참고한 글들이 있습니다!
보다 더 자세한 설명은 해당 블로그들을 참고해주세요.
더보기
'Algorithm > 개념' 카테고리의 다른 글
| 분할 정복 알고리즘 (1) | 2023.04.20 |
|---|
