DFS와 BFS의 정의
DFS와 BFS는 그래프 탐색 알고리즘으로, 그래프 데이터 구조에서 노드를 탐색하는 방법입니다. 대략적으로 500만 개 이하의 경우의 수는 DFS나 BFS를 활용하고 풀고 그보다 더 높은 경우의 수는 DP(다이나믹 프로그래밍)을 이용하여 풀이합니다.
1. DFS (깊이 우선 탐색)
DFS는 시작 노드에서 출발하여 다음 분기로 넘어가기 전에 해당 분기를 완전히 탐색하는 방식입니다. 스택(Stack) 또는 재귀 함수를 사용하여 구현할 수 있습니다. DFS는 더 깊은 단계의 노드를 먼저 탐색하고, 그래프의 깊은 부분을 우선적으로 탐색하는 특징이 있습니다.
2. BFS (너비 우선 탐색)
BFS는 시작 노드에서 가까운 노드부터 차례대로 탐색하는 방식입니다. 큐(Queue)를 사용하여 구현할 수 있습니다. BFS는 시작 노드에서 인접한 노드를 먼저 모두 탐색한 후, 다음 레벨의 노드로 이동하여 탐색하는 특징이 있습니다.
문제 푸는 절차
1. DFS 문제 풀이 방법:
깊이 우선 탐색(DFS) Flood fill
https://www.youtube.com/watch?v=M48Po-wTOpU
- 시작 노드를 선택하고, 스택에 넣습니다.
- 스택이 비어질 때까지 다음 단계를 반복합니다:
- 스택에서 노드를 POP 합니다.
- 해당 노드를 방문 처리하고, 원하는 목표에 도달했는지 확인합니다.
- 인접한 미방문 노드를 스택에 넣습니다.
2. BFS 문제 풀이 방법:
너비 우선 탐색(BFS) Shortest path
https://www.youtube.com/watch?v=RxT7F6YA3TI
- 시작 노드를 선택하고, 큐에 넣습니다.
- 큐가 비어질 때까지 다음 단계를 반복합니다:
- 큐에서 노드를 디큐합니다.
- 해당 노드를 방문 처리하고, 원하는 목표에 도달했는지 확인합니다.
- 인접한 미방문 노드를 큐에 인큐합니다.
특히, 경로 탐색 문제는 BFS로 풀어야 한다. DFS는 알고리즘 특성 상 모든 경우를 탐색한 후 최단 거리를 찾아야 한다.
DFS와 BFS는 다양한 그래프 문제를 해결하는 데 사용되며, 문제의 특성에 따라 적절한 알고리즘을 선택하여 적용합니다.
DFS, BFS 문제
대표적인 유형 : 경로 탐색, 네트워크, 조합 만들기 등.
1260 - DFS와 BFS
1303 - 전쟁 - 전투
2178 - 미로 탐색
1743 - 음식물 피하기
2606 - 바이러스
16930 - 달리기
16953 - A → B
12851 - 숨바꼭질2
13549 - 숨바꼭질3
13913 - 숨바꼭질 4
14226 - 이모티콘
17086 - 아기상어2
