[인프런] DFS & BFS
by 브이담곰📘 10주완성 C++ 코딩테스트 강의를 수강한 후 정리한 글입니다.
깊이 우선 탐색 ( DFS, Depth First Search )
DFS는 그래프를 탐색할 때 쓰는 기법이다.
어떤 노드부터 시작해 인접한 노드들은 재귀적으로 방문하며 방문한 정점은 다시 방문하지 않는다.
각 분기마다 가능한 가장 멀리 있는 노드까지 탐색하는 알고리즘이다.
DFS를 구현하는 방법
1️⃣ visited를 확인하고 함수 호출
2️⃣ 함수 호출 후 기저조건으로 함수 return
⬇ 수도코드
DFS( u , adj )
u.visited = true // 해당 노드 방문처리
for each v in adj[u]
if v.visited == false //방문 여부 확인
DFS( v, adj )// 방문하지 않은 경우 방문( 재귀 )
너비 우선 탐색 ( BFS, Breadth First Search )
BFS는 그래프를 탐색할 때 쓰는 기법이다.
어떤 정점에서 시작해 다음 깊이의 정점으로 이동하기 전 현재 깊이의 모든 정점을 탐색하며 방문한 정점은 다시 방문하지 않는 알고리즘.
같은 가중치를 가진 그래프에서 최단거리 알고리즘으로 쓰인다.
BFS를 구현하는 방법
Queue를 이용한다.
⬇ 수도코드
BFS( G, u )
u.visited = 1
q.push(u)
while( q.size() )
u = q.front()
q.pop()
for each v in G.adj[u] //같은 깊이의 노드 방문
if v.visited == false // 같은 정점 재방문 불가
v.visited = u.visited + 1 //최단거리를 도출해낼 수 있음
q.push(v)
DFS와 BFS 비교
둘 다 시간복잡도는 인접리스트로 이루어져 있다면, O( V + E ) 이고, 인접 행렬의 경우 O( V**2 )
DFS
1. 메모리를 덜 쓴다.
2. 절단점을 구할 수 있다.
3. 코드가 좀 더 짧으며, 완전탐색의 경우에 많이 쓴다.
BFS
1. 메모리를 DFS 보다 더 쓴다.
2. 가중치가 같은 그래프 내에서 최단거리를 구할 수 있다.
3. 코드가 더 길다.
'Computer Science > 자료구조,알고리즘' 카테고리의 다른 글
[인프런] 비트 마스킹 (0) | 2024.02.19 |
---|---|
[인프런] BIG-O 표기법 (0) | 2023.02.02 |
[자료구조] 연결리스트(1) : 리스트를 역순으로 만드는 연산 (0) | 2021.12.04 |
블로그의 정보
농담곰담곰이의곰담농
브이담곰