[알고리즘/탐색] DFS, BFS

DFS와 BFS의 목적

- 임의의 시작점에서 시작해서 모든 정점을 한번씩 방문하는 것

- 경로 찾는 문제에서 활용

 

DFS

- Depth First Search (깊이 우선 탐색)

- 스택을 이용해서 갈 수있는 만큼 최대한 많이 가고, 

  갈 수 없으면 이전 정점으로 돌아가서 갈 수 있는 길을 탐색

- 재귀 호출을 이용해서 구현할 수 있다

 dfs(x) : x에 방문

- 모든 경로를 방문해야 할 경우 사용에 적합

- 시간복잡도 : 인접 행렬 -> O(v^2) : 한 정점당 v번 탐색, 모든 정점 한번씩 방문해야하므로 v * O(v)

                      인접 리스트 -> O(V+E) : 다 끝났을 시점에는 모든 정점을 한번씩 방문하고,

                                                           모든 간선을 한번씩 검사하게 되므로

 

BFS

- 큐를 이용해서 지금 위치에서 갈 수 있는 것을 모두 큐에 넣는 방식

  (해당 노드의 주변부터 탐색해야 하기 때문)

- 최소 비용 (즉, 모든 곳을 탐색하는 것보다 최소 비용이 우선일 때)에 적합

- 큐에 넣을 때 방문했다고 체크해야 한다

- 시간복잡도 : 인접 행렬 -> O(v^2) : 한 정점당 v번 탐색, 모든 정점 한번씩 방문해야하므로 v * O(v)

                      인접 리스트 -> O(V+E) : 다 끝났을 시점에는 모든 정점을 한번씩 방문하고,

                                                           모든 간선을 한번씩 검사하게 되므로

 

 

 

 

 

 

참고:

- 코드 플러스 'SW 역량 테스트 준비 - 기초' 강의

- https://velog.io/@kjh107704/%EA%B7%B8%EB%9E%98%ED%94%84-BFS%EC%99%80-DFS