너비 우선 탐색

• 그래프 탐색 알고리즘 중 하나로 같은 깊이에 해당하는 정점부터 탐색해나가는 알고리즘

특징

• Queue를 이용하여 구현할 수 있다.
• 시작 지점에서 가까운 정점부터 탐색한다.
• V가 정점의 수, E가 간선의 수 일 때 시간복잡도는 O(V+E)이다.

동작 과정

1. Queue에 시작점을 넣는다.
2. 시작점을 dequeue 하고, 시작점으로부터 이동할 수 있는 간선들을 체크하여 해당 정점들을 Queue에 모두 enqueue 한다.
3. 방문한 노드는 다시 enqueue하지 않는다.
4. 더 이상 갈 정점이 없을 때까지 반복한다.
   
   

깊이 우선 탐색

• 최대한 깊은 정점부터 탐색하는 알고리즘

A를 시작점으로 깊이 우선 탐색 시 A, B, F, C, G, D, E 순으로 방문한다.

처음에는 왜 A, B, F 다음에 G를 먼저 방문하지 않는지 헷갈렸다. 위 그래프를 마치 트리처럼 생각해서 G가 더 깊이가 깊은 것 아닌가? 하는 생각이었다.
DFS의 동작원리를 보고나서 왜 저런 순으로 진행되는 지 이해할 수 있었다. DFS는 BFS와 달리 연결된 모든 정점을 넣는 것이 아니라, 하나씩 Stack에 쌓는다. 위 그래프는 실제적으로는 {A : B, C, D}, {B : A, C, F}, {C: A, F}, ... 와 같은 형태로 저장되어 있을 것이다. 따라서 A 정점을 방문 하면 B를 넣고, 다음 B 정점을 방문하면 C를 넣고, C 정점을 방문하면 F를 넣을 것이다. 방문한 순간 연결 정보에서 첫 노드를 빼서 쌓는다고 생각하면 쉽다.

특징

• Stack을 이용하여 구현할 수 있다.
• 시작 정점에서 깊은 것 부터 찾는다
• V가 정점의 수, E가 간선의 수 일 때 시간복잡도는 O(V+E)이다. (BFS와 동일)

동작 과정

1. Stack에 시작점을 넣는다.
2. Stack의 top을 참고하여 이동할 수 있는 정점을 Stack에 하나씩 추가한다. (반복)
3. Stack의 top에서 이동할 수 있는 정점이 없는 경우 pop한다.
4. Stack이 전부 빌 때까지 2-3을 반복한다.

BFS vs DFS

추가적으로 BFS와 DFS의 차이를 알아보자.

	BFS	DFS
시간 복잡도	O(V+E)	O(V+E)
자료구조	Queue 사용	Stack 사용
최단 경로 문제	시작점으로부터 가까운 깊이부터 찾기 때문에, 최소 거리로 목적지에 도달할 수 있다.	보통 BFS에 비해 더 많은 노드를 순회해야 목적지에 도달 할 수 있다.
시작점과 가까운 노드 찾기	적합	부적합
시작점과 먼 노드 찾기	부적합	적합
게임 또는 퍼즐 문제	부적합, 모든 이웃 노드를 탐색하기 때문에 하나의 결정이 성공일지 실패일지를 파악하는 것이 느리다.	적합, 하나의 결정이 성공일지 실패일지 BFS보다 빠르게 알 수 있다.

출처 : https://www.geeksforgeeks.org/difference-between-bfs-and-dfs/

벨로그 표는 도대체 왜 미리보기랑 다르게 나오는걸까..? 가운데 정렬 했는데...

출처

프로그래머스 데브코스 프론트엔드 Day4 [강의] BFS와 DFS