[BAEKJOON] 11724 연결 요소의 개수

백준 11724 연결 요소의 개수 C++ 풀이 정리

 

11724 연결 요소의 개수

문제 

방향 없는 그래프가 주어졌을 때, 연결 요소 (Connected Component)의 개수를 구하는 프로그램을 작성하시오.

 

첫째 줄에 정점의 개수 N과 간선의 개수 M이 주어진다. (1 ≤ N ≤ 1,000, 0 ≤ M ≤ N×(N-1)/2) 둘째 줄부터 M개의 줄에 간선의 양 끝점 u와 v가 주어진다. (1 ≤ u, v ≤ N, u ≠ v) 같은 간선은 한 번만 주어진다.

 

입력

6 5
1 2
2 5
5 1
3 4
4 6

첫째 줄에 연결 요소의 개수를 출력한다.

 

 

출력

2

 

풀이

방향이 없는 그래프라는 점을 고려해 입력 받고 DFS나 BFS중 한가지를 선택하여 풀면 됨

모든 노드에 대해서 탐색을 수행해야하고, 한개의 노드마다 연결된 노드를 탐색하고 해당 노드를 방문처리

한개의 노드 탐색이 끝나면 연결 요소의 개수++

for (int i = 1; i < n + 1; i++) {
	if (visit[i] == 0) {
		dfs(i);
		cnt++;
	}
}

 

1.  DFS

void dfs(int x) {
	visit[x] = 1;


	for (int i = 1; i < n + 1; i++) {
		int isConnected = graph[x][i];

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

2.  BFS

void bfs(int x) {
	q.push(x);
	visit[x] = 1;

	while (!q.empty()) {
		int nownode = q.front();
		q.pop();

		for (int i = 1; i < n + 1; i++) {
			int isConnected = graph[nownode][i];

			if (isConnected == 1 && visit[i] == 0) {
				q.push(i);
				visit[i] = 1;
			}
		}
	}
}

전체 코드

#include <iostream>
#include <queue>

using namespace std;

// 정점의 개수, 간선의 개수
int n, m;
int graph[1001][1001];
int visit[1001];

int cnt;

queue <int> q;

void dfs(int x) {
	visit[x] = 1;


	for (int i = 1; i < n + 1; i++) {
		int isConnected = graph[x][i];

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

void bfs(int x) {
	q.push(x);
	visit[x] = 1;

	while (!q.empty()) {
		int nownode = q.front();
		q.pop();

		for (int i = 1; i < n + 1; i++) {
			int isConnected = graph[nownode][i];

			if (isConnected == 1 && visit[i] == 0) {
				q.push(i);
				visit[i] = 1;
			}
		}
	}
}

int main(void) {
	cin >> n >> m;

	for (int i = 0; i < m; i++) {
		int u, v;

		cin >> u >> v;

		graph[u][v] = 1;
		graph[v][u] = 1;
	}

	for (int i = 1; i < n + 1; i++) {
		if (visit[i] == 0) {
			dfs(i);
			cnt++;
		}
	}

	cout << cnt << endl;

	return 0;
}