[알고리즘] DFS와 BFS

구현 방식

• 같은 엣지가 입력으로 들어올 수 있다고 적혀있으므로, 엣지를 set을 통해 받는다.
• set을 사용하면 추가적으로 얻을 수 있는 장점은, 입력으로 숫자가 들어오면 자동으로 정렬을 해주기때문에
• 문제에서 숫자가 작은 정점부터 탐색해야하는 부분을 자동으로 해결할 수 있다.

코드

• 최종 코드는 아래와 같다.

const int MAXSIZE = 1001;
bool visited[MAXSIZE] = {};

void solution(int N, int V, vector<set<int>>& graph)
{
	visited[V] = true;
	dfs(V, graph);
	cout << "\n";
	fill(&visited[0], &visited[MAXSIZE], false);
	bfs(V, graph);
}

void dfs(int curr, vector<set<int>>& graph)
{
	cout << curr << " ";
	for (auto& next : graph[curr])
	{
		if (!visited[next])
		{
			visited[next] = true;
			dfs(next, graph);
		}
	}

}

void bfs(int start, vector<set<int>>& graph)
{
	queue<int> q;
	q.push(start);
	visited[start] = true;

	while (!q.empty())
	{
		int curr = q.front();
		cout << curr << " ";
		q.pop();
		for (auto& next : graph[curr])
		{
			if (!visited[next])
			{
				visited[next] = true;
				q.push(next);
			}
		}
	}
}