20250324 - DFS와 BFS 비교

DFS와 BFS 비교

• 시간복잡도 차이는 없다. → 어떤 식으로 구현됐는지에 따라서 차이점만 존재
• DFS → 메모리를 덜 씀. 절단점 등 구할 수 있다. 코드가 좀 더 짧으며 완전탐색의 경우에 많이 사용한다.
• BFS → 메모리를 더 쓴다(Queue). 가중치가 같은 그래프 내에서 최단거리를 구할 수 있음. 코드가 더 길다.

코딩테스트 문제에서 ‘퍼져나간다’, ‘탐색한다’ 이 2글자가 있으면 반드시 DFS, BFS가 생각나야 한다.

dfs(int here) 
{
	if (visited[here]) return;
	visited[here] = 1;
	for (int there : adj[here]) 
	{
		dfs(there);
	}
}

bfs(int here)
{
	queue<int> q;
	visited[here] = 1;
	q.push(here);
	while(q.size())
	{
		int here = q.front(); q.pop();
		for (int there : adj[here])
		{
			visited[there] = visited[here] + 1;
			q.push(there);
		}
	}
}