[BOJ] 11724번: 연결 요소의 개수 (c++)

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

11724번: 연결 요소의 개수

 

방법 1 : dfs 함수내에 하나로

#include <iostream>
#include <vector>

using  namespace std;

const int MAX = 1000;
bool check[MAX + 1];

int dfs(vector<vector<int>>& graph, int node)
{
	// 노드가 0이 아닐 때 : 해당 노드의 자식노드 만큼 순회 
	int len = (node == 0) ? graph.size() - 1 : graph[node].size();
	int cnt = 0;

	for (int i = 0; i < len; ++i)
	{
		// 노드가 0이 아닐 때 : 아직 체크되지 않은 자식 노드로 이동
		int next = (node == 0) ? i + 1 : graph[node][i];
		if (!check[next])
		{
			// 노드가 0일 때만 유의미한 cnt값 --> 연결노드의 개수
			++cnt;
			check[next] = true;
			dfs(graph, next);
		}
	}
	return cnt;
}

int main()
{
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);

	int N, M;
	cin >> N >> M;

	// 인접 리스트로 그래프 만들기
	vector<vector<int>> graph(N + 1, vector<int>());
	for (int i = 0; i < M; ++i)
	{
		int first, second;
		cin >> first >> second;

		graph[first].push_back(second);
		graph[second].push_back(first);
	}

	// 연결요소 개수 출력
	cout << dfs(graph, 0);

	return 0;
}

 

방법 2 : 바깥 for문

#include <iostream>
#include <vector>

using  namespace std;

const int MAX = 1000;
bool check[MAX + 1];

void dfs(vector<vector<int>> &graph, int node)
{
	check[node] = true;

	// 해당 노드의 자식노드 만큼 순회 
	for (int i = 0; i < graph[node].size(); ++i)
	{
		int next = graph[node][i];
		if (!check[next])
		{
			dfs(graph, next);
		}
	}
}

int main()
{
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);

	int N, M;
	cin >> N >> M;

	// 인접 리스트로 그래프 만들기
	vector<vector<int>> graph(N + 1, vector<int>());
	for (int i = 0; i < M; ++i)
	{
		int first, second;
		cin >> first >> second;

		graph[first].push_back(second);
		graph[second].push_back(first);
	}

	
	int cnt = 0;
	for (int i = 1; i <= N; ++i)
	{
		// 아직 체크되지 않은 노드의 모든 자식노드들 순회 후 카운팅
		if (!check[i])
		{
			dfs(graph, i);
			++cnt;
		}
	}
	cout << cnt;

	return 0;
}

 

 

보디시피 방법 1, 방법 2는 별 차이가 없다. 

속도도 차이가 없다 ㅋㅋ