깊이 우선 탐색(DFS) 너비 우선 탐색 (BFS) 에 대하여.

 

코딩테스트 Level. 2 를 풀다 보니 도저히 어떻게 풀어야될지 모르겠는 문제들이 많이 나오는데 그 중 하나가 

깊이 우선 탐색인 (DFS) 와 너비 우선 탐색 (BFS) 문제가 나올 경우이다.

코딩테스트를 문제를 풀면서 처음알게되었는데  아직은 익숙치 않아서 어려운 것 같다. 

아래의 블로그에서 굉장히 설명을 잘 해주신 것 같다. 

 

https://devuna.tistory.com/32

[알고리즘] 깊이 우선 탐색(DFS) 과 너비 우선 탐색(BFS)

 

 

1.DFS 

1) 한 분기를 다 검색한 후에 다음 분기로 넘어가서 검색을 해야 할 경우 . 

예. 미로찾기 할 때 한 경로를 다 갔다가 아닌경우 다시 갈림길로 돌아와 다른 경로를 찾는다. 

 

2.BFS

1) 인접한 분기부터 검색을 해야할 경우. 

예. 최단경로, 제일 친한 인간관계 찾기 등

 

 

 

DFS 는 보통 재귀함수로 코드를 짜는 것이 더 간결하게 짤 수 있다고 한다. 

 

알고리즘 신기한 부분이 많은 것 같다.