깊이 탐색(Depth-First Search)과 너비 탐색 (Breadth-First Search)

개념은 이거 보면 깔끔하쥬?

핵심은 이를 구현하기 위해선 DFS → 재귀, BFS → queue 이다.

보통 재귀가 더 느리지만 코딩하기 간편하고 짧다는 차이가 있다.

DFS

void dfs(...){
	if(/* 정답을 탐색했을 경우 or 끝에 도달할 때 */){
		answer = ...;
		return;
	}
	dfs(...)
}
void solution(...){
	dfs(...); // dfs 탐색 시작
}

여기서 TMI TIP 인수로 넘길 때 call by reference(&) 로 하는 것이 정석. 메모리, 속도에 영향있다.

탐색하면서 역시 경로를 기억해야하는 경우가 상당히 많다. 주어진 배열을 활용하여 메모리 아끼면서 기억해도 되지만 보통 visit 배열을 만든다.

if(...){
	visit[i] = 1;
	dfs(...);
	visit[i] = 0;
}

요롷게 방문하고 다시 초기화 해주는 것이 중요!

BFS

queue에 트리 데이터를 담고 while(!queue.empty()) 돌리면 된다.

기본적인 탐색 구조이다.

#include<queue>
void solution(...){
	queue<string> q;
	q.push("a");
	while(!q.emtpy()){
		string cur = q.front();
		//visit[i] = 1;
		q.pop();
		for(/* 탐색 */)
			if(...){
				q.push(...);
			}
	}
}

q.front() 가 pop된다는 것만 햇갈리지 않으면 될듯.. (본인 경험담.. 아무생각없이 back())