https://github.com/leesk212/PS/tree/main/5014
5014 번 문제를 풀면서 DFS로 풀때는 시간초과가 나고, BFS로 풀때는 시간초과 없이 맞는 것을 확인할 수 있었다.
이에따라, 관성이 필요하다고 느꼈다.
-> 어? DFS 가 시간초과 나네? -> 바로 BFS 구현
그러므로 BFS와 DFS의 차이를 파악하고, 어떤때 어떻게 쓸지 다시 정리해보자 (어차피 프로 딸때 개념적으로 다시 돌아와야한다.)
완전탐색의 개념
- BFS 와 DFS는 모두 완전 탐색의 기법중 하나이다.
- 대신 어떻게 탐색을 할지에 대한 원론적인 차이만 다를 뿐이다.
- DFS의 경우, 깊이 탐색을 진행함으로, 해당 깊이에서 들어갈 수 있는 최대로 들어간다. 그리고 돌아와서 다음 면으로 이동한다.
-
BFS의 경우, 시작 위치에서 갈 수 있는 면(인접한 곳)들을 모두 방문하고, 다음 깊이로 들어간다.
- 따라서 결국 DFS 건 BFS 건 완전탐색을 풀면 풀리는 문제들이다. (하지만, 속도면에서 어떤것이 쓰임이 맞는가는 다른문제)
DFS 의 쓰임
- 가장 깊은 곳을 우선하여 탐색하고, 더 이상 탐색할 수 없으면 백트래킹하여 최근 방문 노드부터 다시 탐색한다는 특징
- 모든 가능한 해를 찾는 백트래킹 알고리즘을 구현할 때나, 그래프의 사이클을 감지해야하는 경우 활용 가능
- 탐색을 해야할 때 최단 경로는 찾는 문제가 아니라면, DFS 를 우선 구현하는 것이 좋다. (EX., 순열, 조합)
- 경로의 특징을 저장해둬야하는 문제
BFS 의 쓰임
- BFS의 장점은 찾은 노드가 시작 노드로부터 최단 경로임을 보장한다.
- –> 이 포인트가 핵심인데, 왜냐하면, 시작 노드로부터 직접 간선으로 연결된 모든 노드를 먼저 방문하기 때문
- 문제에 대한 답이 많은 경우, BFS는 답 중에서도 가장 가까운 답을 찾는데 도움을 준다.
- 미로 찾기 문제나 네트워크 분석 문제를 풀 때 활용할 수 있다.
BFS, DFS 구현
- 각각의 알고리즘의 “방문처리 시점”이 핵심이다.
BFS
- 방문처리를 PUSH하고나서 바로 방문처리 -> 지금 방문할 노드를 푸시하기 때문에 (그래야 인접한 노드 부터 방문 가능)
#include <iostream>
#include <queue>
using namespace std;
void bfs(int start){
queue<int> q;
visited[start] = 1;
while(!q.empty()){
int cur = q.front();
q.pop();
for (int i =0; i<2; i++){
next = cur + d[i];
if(!visited[next]){
q.push(next);
visited[next] = 1; // 핵심! 인접 노드로 바로 가고 싶으면 바로 해줘야함 (로봇청소기 이거 안해서 틀림)
}
}
}
DFS
- 방문처리를 값을 시작할때 처리 (보편적으로)
- 조합 순열 등, 계속해서 값을 확인해야하는 경우가 있으면 방문처리를 다양화해줘야함
- 재귀로 돌린다면, 그 다음값을 들어가서 방문처리해줘도 괜찮음. 다만 재귀를 빠져나오고 나서, 다시 그 방문을 살려야할 경우도 생각해야함
void dfs(int cnt,int cur) {
////////////////////////////////////여기서 방문처리해줘도 괜찮음
if (cur == G) {
ans = cnt;
cout << ans;
exit(1);
}
for (int i = 0; i < 2; i++) {
int next = cur + moving_dir[i];
//혹시라도 층수를 넘겼을 경우! 그냥 넘어가자!
if (next > F || next < 0) continue;
//해당 층수를 방문했으면 굳이 또 방문해야할까? ㄴㄴ
if (visted_floor[next] == 1) continue;
visted_floor[next] = 1;
dfs(cnt + 1, next);
visted_floor[next] = 0;
}
}