bfs & dfs 에 대해 설명해주세요.

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

• 주로 재귀, 스택을 이용하여 구현한다 (재귀 이용시 스택 오버 플로우가 발생할 수 있으므로 이런 경우는 스택을 이용하여 계산하는것이 낫다)

• 루트 노드에서 시작해서 다음 분기로 넘어가기 전 해당 분기를 모두 탐색하는 방식이다.

• 현재 정점에서 가장 깊은곳부터 가보는 방법

• 목표노드에 도착한 경우 모든 경러 탐색 전까지는 최단경로임을 보장할 수 없다.

• 백준 추천 : n,m

• 시간복잡도(V는 접점, E는 간선을 뜻한다.)

  • 인접 행렬: O(V^2)

  • 인접 리스트: O(V+E)

bfs (Breadth-First Search) 너비우선탐색

• 주로 큐를 이용하여 구현한다.

• 최단 경로를 구하는 경우 유리하다.

• 현재 정점에서 인접 노드를 먼저 탐색하는 방법으로 멀리 떨어저 있는 노드를 나중에 방문한다.

• 백준 추천 : 토메이도

• 시간복잡도(V는 접점, E는 간선을 뜻한다.)

  • 인접 행렬: O(V^2)

  • 인접 리스트: O(V+E)