기초(6) DFS, BFS

https://velog.io/@vagabondms/DFS-vs-BFS

[ DFS 깊이 우선 탐색 ]

한 정점에서 출발해 가능한 멀리까지 탐색하는 방법

• 지나온 경로를 쉽게 파악할 수 있다.
• 스택 또는 재귀함수로 구현할 수 있다.

< 재귀함수 구현 >

1. 현재 위치와 깊이를 기본 인자로 가진다.
2. 함수 내부는 종료조건과 탐색 조건으로 나눈다.
3. 탐색 조건은 기존에 방문한 정점이 아닐 경우에만 재귀함수를 호출하여 탐색한다.

< Stack 구현 >

1. 시작 노드를 stack에 push 한다.
2. top 노드를 pop한다.
3. 해당 노드를 방문하지 않았었다면 방문으로 처리한다.
4. 해당 노드의 인접 노드 중 방문하지 않은 노드를 stack에 push한다.
5. 2~4를 반복한다.

void dfs(int depth){
	if(종료 조건){ 
    	//결과 출력
    }
    else {
    	// 탐색
        if(조건에 부합할 경우){
        	//상태 변경
            dfs(depth);
            //상태 원상 복귀
        }
    }
}

---

[ BFS 깊이 우선 탐색 ]

시작 정점으로부터 거리순으로 탐색한다.

• 시작점에서 가까운 목적지를 찾는 데 효율적이다.
• 다익스트라 알고리즘, 벨만-포드 알고리즘, 플로이드 워셜 알고리즘의 근본이다.

< Queue 구현 >

1. 시작점을 큐에 넣는다.
2. 큐에서 한 점을 꺼내서 기준점으로 삼는다.
3. 기준점이 목표로 하는 목적지이면 탐색을 종료한다.
4. 아니라면 기준점에서 갈 수 있는 다음 정점들을 큐에 넣는다.
5. 큐에 원소가 없을 때까지 2단계로 돌아가 반복한다.

//시작점 삽입
que.push(s);
//que가 텅 빌 때까지 반복
while(!que.empty()){
	//맨 앞 데이터 가져오기
	int now = que.front();
    que.pop();
    if(종료 조건){
    	//결과
    }
    else{
    	//탐색
    }
}

---

[ 어떤 문제에 DFS와 BFS를 사용해야 하는가? ]

< DFS 깊이 우선 탐색 = 모든 경우의 수, 경로의 특징 >

• 모든 경우의 수를 탐색해야 하는 문제
  순열, 조합
• 미로 찾기
  한 경로를 끝까지 탐색하는 특성이 미로 탐색에 적합하다.
  
  
• 그래프가 큰 경우
  메모리를 덜 사용한다.

< BFS 깊이 우선 탐색 = 최단 경로 >

• 최단 경로 문제
  가까운 노드부터 탐색하기 때문에 최단 경로를 보장한다.
• 레벨 단위의 탐색
  
  
• 탐색 시작 지점과 가까운 곳에 답이 있는 경우
  
  
• 네트워크 탐색
  연결된 모든 노드를 효율적으로 탐색한다.