[코테 대비] BFS/DFS 정리 + 차이점

[코딩테스트 대비] DFS, BFS 정리

 

DFS, BFS의 설명, 차이점

이해가 쏙쏙 되게끔 잘 적어주셔서.. 나도 잊어버리지 않게 메모! 유익한 정보 감사합니다 😄

 

 

DFS(깊이 우선 탐색)

루트 노드(혹은 다른 임의의 노드)에서 시작해서 다음 분기로 넘어가기 전에 해당 분기를 완벽하게 탐색하는 방식.

미로찾기를 할 때 최대한 한 방향으로 갈 수 있을 때까지 쭉 가다가 더 이상 갈 수 없게 되면

다시 가장 가까운 갈림길로 돌아와서 그 갈림길부터 다시 다른 방향으로 탐색을 진행하는 것이 DFS.

 

     1. 모든 노드를 방문하고자 하는 경우

     2. DFS가 BFS보다 더 간단함

     3. 검색 속도: BFS>DFS

 

 

BFS(너비 우선 탐색)

루트 노드(혹은 다른 임의의 노드)에서 시작해서 인접한 노드를 먼저 탐색하는 방법으로,
시작 정점으로부터 가까운 정점을 먼저 방문하고 멀리 떨어져 있는 정점을 나중에 방문하는 순회 방법.

주로 두 노드 사이의 최단경로를 찾고 싶을 때 선택.

 

만약 모든 사람들의 관계를 그래프로 표현한 다음, A와 B사이에 존재하는 경로를 찾는 경우

     - DFS = 모든 관계를 확인(방문)해야할 수 있음

     - BFS = A랑 가까운 관계부터 확인

 

 

📌 그래프의 모든 정점을 방문해야 한다.

     = 단순 방문일 시 DFS/BFS 상관 없음.

 

📌 경로의 특징을 저장해야 한다.

     = 정점마다 숫자가 적혀있고, 경로상에서 같은 숫자가 있으면 안되는 등 경로마다 특징이 필요할 경우 DFS

     = BFS는 경로의 특징을 가질 수 없음

 

📌 최단거리 문제

     = 미로찾기 등 최단거리 찾는 문제는 BFS가 유리.

     = DFS로 검색할 경우 처음 찾은 해답이 최단거리가 아닐 수 있음

     = BFS는 가까운 곳 부터 찾기 때문에 경로 탐색시 제일 처음 찾은 답이 최단거리

 

📌 검색 대상 그래프가 너무 크면 DFS

📌 검색 대상 규모가 크지 않고, 검색 시작 지점부터 원하는 대상이 별로 멀지 않으면 BFS