코딩 테스트 유형보기 2 - DFS / BFS

유형보기 2 - DFS / BFS

---

---

DFS 와 BFS

---

내용출처 

https://covenant.tistory.com/132

https://velog.io/@lucky-korma/DFS-BFS%EC%9D%98-%EC%84%A4%EB%AA%85-%EC%B0%A8%EC%9D%B4%EC%A0%90

 

 

1. 깊이 우선 탐색 ( DFS : Depth-First Search )

최대한 깊이 내려간 뒤, 더 이상 깊이 갈 곳이 없을 경우 옆으로 이동

출처 https://developer-mac.tistory.com/64

 

깊이 우선 탐색의 개념 및 이해

• 루트 노드 ( 혹은 다른 임의의 노드 ) 에서 시작해서 다음 분기로 넘어가기 전에, 해당 분기를 완벽하게 탐색
• 최대한 한 방향으로 갈 수 있을 때 까지 가다가 더 이상 못 가게 되면 되돌아가는 방식

2. 너비 우선 탐색 ( BFS : Breadth-First Search )

최대한 넓게 이동한 다음, 더 이상 갈 수 없을 때 아래로 이동

출처 https://developer-mac.tistory.com/64

 

너비 우선 탐색의 개념 및 이해

• 루트 노드 ( 혹은 다른 임의의 노드 ) 에서 시작해서 인접한 노드를 먼저 탐색
• 시작 노드로 부터 가까운 애들 먼저 찾아보는 방식

 

3. DFS 와 BFS 의 비교

 

	DFS ( 깊이 우선 탐색 )	BFS ( 너비 우선 탐색)
정의	현재 노드에서 갈 수 있는 점까지 깊게 들어가며 탐색	현재 노드에서 가까운 점들부터 탐색
구현	스택 / 재귀 함수로 구현	큐 이용해서 구현
시간복잡도	N : 노드 / E : 간선 인접리스트 : O(N+E) 인접행렬 : O(N^2)	N : 노드 / E : 간선 인접리스트 : O(N+E) 인접행렬 : O(N^2)

 

DFS 장단점 및 사용

장점

• 현 경로상의 노드를 기억하기 때문에 적은 메모리를 사용한다.
• 찾으려는 노드가 깊은 단계에 있는 경우 BFS 보다 빠르게 찾을 수 있다.

단점

• 해가 없는 경로를 탐색할 경우, 단계가 끝날때까지 탐색한다.
  - 효율성을 높이기 위해서 미리 지정한 임의 깊이까지만 탐색하고 해를 발견하지 못하면 빠져나와
    다른 경로를 탐색하는 방법을 사용
• DFS를 통해 얻어진 해가 최단 경로라는 보장이 없다. DFS는 해에 도착하여 탐색을 종료하기 때문

 

BFS 장단점 및 사용

장점

• 답이 되는 경로가 여러 개인 경우에도 최단경로임을 보장한다.
• 최단 경로가 존재하면 깊이가 무한정 깊어진다고 해도 답을 찾을 수 있다.
  - DFS에서는 깊이가 무한정이면 다른 경로탐색도 전에 계속 그경로를 탐색하고있기때문에 안되는건가?

단점

• 경로가 매우 길 경우에는 탐색 가지가 급격히 증가함에 따라, 보다 많은 기억공간을 필요하게 됨
• 해가 존재하지 않는다면 유한 그래프의 경우에는 모든 그래프를 탐색한 후에 실패로 끝난다.
• 무한 그래프의 경우에는 결코 해를 찾지도 못하고, 끝내지도 못함