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

* 참고로 https://blog.naver.com/kks227/220785731077 이 사이트에서 알고리즘을 많이 공부하였고, 그것을 바탕으로 정리하고 있다. 사실 알고리즘을 정리하게 된 이유는 무려 이번주 금요일에 네이버 기술면접이 있기 때문이다. CS도 준비해야 할 것 같은데, 내 학부는 "근본 컴공"이 아니라서..ㅜ 중요한 것 몇 개만 공부할 예정이다. 포스텍 AI 대학원 시험 볼 때도 따로 공부했던 (시험에는 안 나왔었던 것 같다. 근데 면접에서 나온 것 같기도) DFS, BFS를 먼저 정리한다. 사실 최근 네이버 코딩 테스트를 준비하며 공부했는데 이 개념이 코테에서 꽤나 자주 나와서 알고리즘 중 가장 중요하면서 간단한 것은 이게 아닐까.. 싶다. (지극히 개인적인 의견) 

 

• DFS, BFS둘다 컴포넌트*의 모든 정점을 한 번씩 순회하는 용도의 알고리즘

             *컴포넌트(연결 요소): edge로 연결된 그래프

출처: https://blog.naver.com/kks227/220785731077

 

DFS (Depth first search)는 말 그대로 깊이를 우선적으로 탐색하는 것이다. ex) 트리 구조인 컴포넌트를 탐색할 때, 탐색한 노드의 옆노드 대신, 아래 노드로 아래노드로 점점 내려가면서 탐색하는 것이다. 아래 그림을 예시로 살펴보자. 

그림 1

현재 탐색 중인 노드가 하늘색이라면, DFS가 탐색할 다음 노드는 노란색이다. (그림 1)

 

BFS (Breadth first search) 역시 말 그대로 너비를 우선적으로 탐색하는 알고리즘이다. ex) 트리 구조의 컴포넌트를 탐색할 때, 한 노드의 탐색이 끝나면 아래로 내려가지 않고, 같은 서열의 노드를 먼저 탐색하는 것이다. 

위의 그림(그림 1)에서 보면, 현재 노드가 하늘색일 때, BFS는 하늘색이 탐색이 끝나면 빨간색 노드를 살펴본다.

 

즉 DFS와 BFS는 아래로 내려가냐 옆으로 가냐 차이가 있다. 

 

 

구체적인 알고리즘 코드는 다음 글에서 살펴보자.