[알고리즘] DFS와 BFS

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

---

• 그래프 탐색
• 임의의 노드에서 다음 분기(branch)로 넘어가기 전에 해당 분기를 완벽하게 탐색하는 방법
• 구현이 너비 우선 탐색(BFS) 보다 간단함, 단순 검색 속도는 너비 우선 탐색(BFS) 보다 느림
• 전위 순회 등 트리 순회는 모두 DFS의 한 종류
• 해가 없는 경우에 빠질 가능성이 있음
• 깊이 우선 탐색은 해를 구하면 탐색이 종료되므로, 구한 해가 최단 경로가 된다는 보장이 없음
• 어떤 노드를 방문했었는지 여부를 반드시 검사 해야 한다(check, visited 등)
• 1)스택을 사용 2)재귀사용

예시

• 프로그래머스 여행 경로 링크

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

---

• 그래프 탐색
• 두 노드 사이의 최단 경로 혹은 임의의 경로를 찾고 싶을 때 주로 사용
• 시작 정점으로부터 가까운 정점을 먼저 방문하고 멀리 떨어져 있는 정점을 나중에 방문하는 순회 방법
• BFS는 재귀적으로 동작하지 않는다
• 선입선출(FIFO) 원칙으로 탐색
• 'Prim', 'Dijkstra' 알고리즘과 유사
• 큐에 다음에 탐색할 정점들을 저장해야 하므로 저장공간이 많이 필요하다.
• 방문한 노드들을 차례로 저장한 후 꺼낼 수 있는 큐를 사용

예시

• 프로그래머스 네크워크 링크
• 프로그래머스 가장 먼 노드 링크