DFS(깊이 우선 탐색)과 BFS(너비 우선 탐색)

1️⃣  DFS (깊이 우선 탐색)

그래프 완전 탐색 기법 중 하나로, 그래프의 시작 노트에서 출발하여 탐색할 한 쪽 분기를 정하여 최대 깊이까지 탐새을 마친 후 다른 쪽 분기로 이동하여 다시 탐색을 수행하는 알고리즘

(완전 탐색이란 그래프에 있는 모든 노드를 탐색하는 것)

 

 

특징

-  재귀 함수로 구현

-  스택(Stack) 자료구조 이용

-  시간 복잡도는 O(V+E)    V : 노드 수, E : 예지 수

 

깊이 우선 탐색을 응용하여  풀 수 있는 문제

단절점 찾기, 단절선 찾기, 사이클 찾기, 위상 정렬, ...

 

 

 

 

DFS 핵심 이론

DFS는 한 번 방문한 노드를 다시 방문하면 안 되므로 노드 방문 여부를 체크할 배열이 필요하다.

그래프는 인접리스트로 표현하고, 스택을 사용하여 DFS를 구현해보자.

 

 

1)  시작 노드를 정한 후 사용할 자료 구초 초기화

 

-  인접 리스트로 그래프 표현

-  방문 배열 초기화

-  스택에 시작 노드 삽입

 

이미지 출처 : Do it! 알고리즘 코딩 테스트 - DFS

 

 

 

2)  스택에서 노드를 꺼낸 후 꺼낸 노드의 인접 노드를 다시 스택에 삽입

 

스택에 노드를 삽입할 때 방문 배열을 체크하고, 스택에서 노드를 뺄 때 탐색 순서에 기록하며 인접 노드를 방문 배열과 대조하여 살펴본다.

 

이미지 출처 : Do it! 알고리즘 코딩 테스트 - DFS

 

 

 

3)  스택 자료구조에 값이 없을 때까지 위 과정을 반복

 

이미 다녀간 노드는 방문 배열을 바탕으로 재삽입하지 않도록 한다.

 

이미지 출처 : Do it! 알고리즘 코딩 테스트 - DFS

 

 

DFS 관련 문제

✅  백준  -  연결 요소의 갯수

✅  프로그래머스  -  DFS/BFS

 

 

 

 

 

 

 

2️⃣  BFS (너비 우선 탐색)

그래프 완전 탐색 기법 중 하나로, 시작 노드에서 출발해 시작 노드를 기준으로 가까운 노드를 먼저 방문하면서 탐색하는 알고리즘

 

 

특징

-  FIFO 탐색

-  큐(Queue) 자료구조 이용

-  시간 복잡도는 O(V+E)    V : 노드 수, E : 예지 수

-  시작 노드와 가까운 노드를 우선 탐색하므로 목표 노드에 도착하는 경로가 여러 개 일 때 최단 경로를 보장

 

 

 

 

BFS 핵심 이론

DFS와 마찬가지로 방문했던 노드를 다시 방문하지 않기 위해 방문한 노드를 체크하기 위한 배열이 필요하다.

그래프를 인접 리스트로 표현하고, 큐 자료구조를 이용하여 BFS를 구현해보자.

 

 

1)  시작 노드를 정한 후 자료구조 초기화

 

-  인접 리스트로 그래프 표현

-  방문 배열 초기화

-  큐에 시작 노드 삽입

 

이미지 출처 : Do it! 알고리즘 코딩 테스트 - BFS

 

 

 

2)  큐에서 느드를 꺼낸 후 노드의 인접 노드를 다시 큐에 삽입

 

이미지 출처 : Do it! 알고리즘 코딩 테스트 - BFS

 

 

 

3)  큐 자료구조에 값이 없을 때까지 위 과정을 반복

 

이미지 출처 : Do it! 알고리즘 코딩 테스트 - BFS

 

 

 

BFS 관련 문제

✅  백준  -  미로 탐색

✅  프로그래머스  -  DFS/BFS

 

 

 

 

 

 

참고 자료

🔗 [하루코딩]  알고리즘 코딩테스트 핵심이론 강의 - DFS ( 깊이 우선 탐색 )

🔗 [하루코딩]  알고리즘 코딩테스트 핵심이론 강의 - BFS ( 너비 우선 탐색 )