[Algorithm] DFS와 BFS

🙇‍♀️ 언제 사용할까?

DFS: 노드가 깊이 존재할 때 해를 빠르게 구할 수 있다. 그러나 해가 없는 경로로 빠질 수 있다. 또한 구한 해가 최적이 아닐 수 있다.

BFS: 따라서 특정 조건의 최단 경로 알고리즘을 계산할 때 BFS를 사용한다. 또한 DFS에 비해 메모리를 많이 필요로 한다. 또한 무한 그래프일 경우 해를 찾지 못하고 무한 루프에 빠진다.

DFS

재귀함수나 스택으로 구현할 수 있다.

1. 탐색 시작 노드를 스택에 삽입 후 방문처리
2. 스택의 최상단 노드에 방문하지 않은 인접한 노드가 하나라도 있으면 그 노드를 스택에 넣고 방문처리, 방문하지 않은 인접 노드가 없으면 스택에서 최상단 노드를 꺼낸다.
3. 2번 반복

*방문 여부를 반드시 검사!!(무한 루프에 빠질 수 있음)

BFS

큐를 사용하여 구현할 수 있다.

1. 탐색 시작 노드를 큐에 삽입 후 방문처리
2. 큐에서 노드를 꺼낸 뒤 방문하지 않은 인접 노드를 모두 큐에 삽입 후 방문 처리
3. 2번 반복

• BOJ 36
• Algorithm 12
• CodingTest 11
• Web 9
• Javascript 8
• Vue 7
• React 7
• DBProject 4
• Python 3
• Tech-interview 3
• Express 3
• Next 3
• Github 2
• Django 2
• C 1
• C++ 1
• WebGame 1