[BFS] BOJ 11724 : 연결 요소

백준 알고리즘 강의를 토대로 작성된 문제풀이입니다.
DFS 와 BFS 의 개념에 대해서는 지난 포스트를 봐주세요.
DFS : 2019/05/23 - [프로그래밍/알고리즘] - [알고리즘] 깊이 우선 탐색(DFS, Depth-First Search)
BFS : 2019/05/26 - [프로그래밍/알고리즘] - [알고리즘] 너비 우선 탐색(BFS, Breadth-First Search)
예제 : 2019/07/22 - [프로그래밍/1일1백준] - [Graph] BOJ 1260 : DFS 와 BFS

 

 

문제

---

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

입력

---

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

 

 

출력

---

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

풀이

---

 

 

 

바로 직전 포스트에서 for문 하나만 추가하면 풀 수 있는 간단한 문제입니다.

직전 포스트는 여기로 가시면 됩니다.

 

 

정점이 1, 2, 3, 4 네개가 있는데

1 - 2 , 3 - 4 이렇게 간선은 두 개만 연결되어 있다고 합시다.

 

 

이 상태에서 일반적인 bfs(1)을 하게 되는 경우

즉, 1을 시작으로 너비 우선 탐색을 하는 경우 1과 2를 탐색하고

더 이상 연결되어있는 정점이 없기때문에 탐색을 마치게 됩니다.

 

 

그래서!! 저희는 모든 정점을 돌기위해서 모든 정점을 시작점으로 해주는

for문을 만들게 됩니다.

이때 주의하실점은 이미 탐색을 한 정점은 넘어가야 한다는 겁니다.

이렇게 for문을 통해서 bfs를 시작할 때마다 연결 요소의 개수를 하나씩 체크만 해주면

문제는 해결됩니다.

 

더 자세한 설명을 원하시면 댓글을 통해 말해주세요. ㅎㅎ

코드는 정답 코드와 연결 요소 내부의 정점들을 모두 표시한 코드를 올려놨습니다.

 

 

 

 

정답 코드

---

 

#include <iostream>
#include <vector>
#include <queue>
using namespace std;

vector<int> a[1001];
bool check[1001];

void bfs(int node) {
			bool end = true;
			queue <int> q;
			check[node] = true;
			q.push(node);

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

				for (auto elements : a[next]) {
					if (!check[elements]) {
						q.push(elements);
						check[elements] = true;
					}
				}

			}
		}
	



int main() {

	int u, v;
	cin >> u >> v;

	for (int i = 0; i < v; i++) {
		int x, y;
		cin >> x >> y;
		a[x].push_back(y);
		a[y].push_back(x);
	}
	int components = 0;
	for (int i = 1; i <= u; i++) {
		if (check[i] == false) {
			bfs(i);
			components += 1;
		}
	}
	cout << components;
	return 0;
}

 

 

노드 값을 전부 출력한 코드

---

#include <algorithm>
#include <iostream>
#include <vector>
#include <queue>
using namespace std;

vector<int> a[1001];
bool check[1001];
int component = 0;

void bfs(int u) {
	for (int node = 1; node < u;node++) {
		if (!check[node]) {
			cout << "---------" << component + 1 << "번째 연결요소------" << '\n';
			bool end = true;
			queue <int> q;
			check[node] = true;
			cout << node << ' ';
			q.push(node);

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

				for (auto elements : a[next]) {
					if (!check[elements]) {
						q.push(elements);
						cout << elements << ' ';
						check[elements] = true;
					}
				}

			}
			cout << '\n';
			component++;
		}
	}
	cout << "연결요소 : " << component << endl;
}


int main() {

	int u, v;
	cin >> u >> v;

	for (int i = 0; i < v; i++) {
		int x, y;
		cin >> x >> y;
		a[x].push_back(y);
		a[y].push_back(x);
	}

	bfs(u);
	return 0;
}