[백준/C++] 11724번 연결 요소의 개수 / BFS 풀이

백준 11724번 BFS

 

11724번 BFS 풀이

이 문제는 일반적인 BFS 형식과는 조금 달라서 헤맸다. 

상하좌우 탐색이 아닌, 모든 정점을 탐색해야해서 DFS로의 풀이도 가능하다. 

 

모든 탐색을 해야해서 vector 함수를 이용해서 들어오는 인자값들을 입력해줬다. 한방향이 아니라 양방향이라 두 개다 넣어준 것이다. 

	for (int i = 0; i < m; i++) {
		int u, v;
		cin >> u >> v;
		vec[u].push_back(v);
		vec[v].push_back(u);
	}

 

BFS 함수안 형식도 비슷하지만, 역시나 vector의 사이즈와 들어있는 인자값을 통해 조절해주는 포인트가 중요하다. 탐색시 vis라는 방문 인자를 1로 바꿔주는 것도 중요하다.

 

 

---

11724 백준 전체코드 

#include <iostream>
#include <queue>
#include <vector>
using namespace std;
#define X first
#define Y second
int vis[1002];
vector<int> vec[1002];


void Bfs(int start) {
	vis[start] = 1;
	queue<int> Q;
	Q.push(start);

	while (!Q.empty()) {

		int cur = Q.front(); Q.pop();

		for (int i = 0; i < vec[cur].size(); i++) {
			if (vis[vec[cur][i]] == 0) {
				Q.push(vec[cur][i]);
				vis[vec[cur][i]] = 1;
			}
		}
	}
	
}

int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);
	int n, m;
	cin >> n >> m;
	for (int i = 0; i < m; i++) {
		int u, v;
		cin >> u >> v;
		vec[u].push_back(v);
		vec[v].push_back(u);
	}
	int result = 0;
	

	for (int i = 1; i <= n; i++) {
		if (vis[i] == 0) {
			Bfs(i);
			result++;
			//cout << i << '\n';
		}
	}
	
	cout << result << '\n';

}