항해중인 개발자

DFS & BFS 본문

Algorithm

DFS & BFS

바다를바라보다 2021. 3. 11. 17:26

DFS = Depth First Search = 깊이 우선 탐색

최대한 깊이 들어가본다

BFS = Breadth First Serch = 넓이 우선 탐색

최대한 넓게 본다

 

미로를 예로 들면, 

DFS는 틀린길일 지라도 최대한 깊게 들어가서 길이 없는걸 확인하고 돌아온다.

BFS는 끝까지 들어가는게 아니라 확인하고 나서 다른길로 들어간다.

 

www.youtube.com/watch?v=-wsYtm0x3nw&t=301s

컴퓨터에서는 어떻게 쓰일까?

 

트리라고 불리는 구조를 볼 수 있는데 

아래를 보면 쉽게 이해 할 수 있을 것이다.

1. 루트 노드부터시작

2. 현재 방문한 노드를 visited에 추가

3. 현재 방문한 노드와 인접한 노드 중 방문하지 않은 노드에 방문한다

4. 2부터 반복한다FS = Depth First Search = 깊이 우선 탐색

최대한 깊이 들어가본다

 

BFS = Breadth First Serch = 넓이 우선 탐색

최대한 넓게 본다

 

 

 

미로를 예로 들면, 

DFS는 틀린길일 지라도 최대한 깊게 들어가서 길이 없는걸 확인하고 돌아온다.

 

BFS는 끝까지 들어가는게 아니라 확인하고 나서 다른길로 들어간다.

 

www.youtube.com/watch?v=-wsYtm0x3nw&t=301s

 

컴퓨터에서는 어떻게 쓰일까?

 

 

 

트리라고 불리는 구조를 볼 수 있는데 

 

아래를 보면 쉽게 이해 할 수 있을 것이다.

 

1. 루트 노드부터시작

 

2. 현재 방문한 노드를 visited에 추가

 

3. 현재 방문한 노드와 인접한 노드 중 방문하지 않은 노드에 방문한다

 

4. 2부터 반복한다

'Algorithm' 카테고리의 다른 글

백준 28258 큐 2  (0) 2021.03.16
백준 4948 베르트랑 공준 풀이  (0) 2021.03.13
잡다한 글 DFS  (0) 2021.03.11
DFS & BFS  (0) 2021.03.11
0 Comments
댓글쓰기 폼