DFS & BFS

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부터 반복한다