[알고리즘/탐색] DFS (깊이 우선 탐색)

깊이 우선 탐색?

그래프 완전 탐색 기법 중 하나.

시작 노드에서 출발, 한쪽 분기로 최대 깊이 까지 탐색한 후, 다른 쪽 분기로 이동하여 최대 깊이까지 탐색, 이를 반복하는 알고리즘.

 

노드 수 : V, 에지 수 : E 일 때

시간 복잡도 : O(V+E) 

구현 시 재귀 함수를 이용하므로 스택 오버플로*에 주의!

 

*스택 오버플로 : 재귀 함수가 호출 될 떄마다 스택 영역에 프레임이 쌓여 스택 메모리가 과부하를 겪는 현상.

재귀 함수 사용 시 중단 조건을 정확히 설정하자.

 

백준 : 11724번

https://www.acmicpc.net/problem/11724

#include <iostream>
#include <vector>

std::vector<std::vector<int>> edges;
std::vector<bool> visited;

void DFS(int node)
{
	if (visited[node])
	{
		return;
	}
	visited[node] = true;
	for (const int& i : edges[node])
	{
		DFS(i);
	}
}

int main()
{
	std::ios::sync_with_stdio(false);
	std::cin.tie(NULL);
	std::cout.tie(NULL);

	int N, M;
	std::cin >> N >> M;
	int count = 0;

	edges.resize(N+1,std::vector<int>());
	visited.resize(N + 1, false);
	while (M--)
	{
		int s, e;
		std::cin >> s >> e;
		edges[s].push_back(e);
		edges[e].push_back(s);
	}
	for (int i = 1; i <= N; ++i)
	{
		if (visited[i])
		{
			continue;
		}
		else
		{
			++count;
			DFS(i);
		}
	}
	std::cout << count;
}