[C++] 백준/BOJ - 11724 : 연결 요소의 개수

문제 이해 단계

---

짧아서 이해하기 간단한 문제

 

N개의 점과 M개의 선이 입력된 후,
그 아래에 연결 노드의 정보들이 입력된다.


그때의 연결 노드의 개수를 구하는 문제이다.

 

 

 

문제 접근 단계

---

BFS나 DFS로 푸는 대표적인 연습용 문제라서
유추할 필요도 없다.

 

방향이 없는 그래프이기 때문에
양쪽 모두 연결된다는 점만 기억하면 된다.


예를 들어, 2 5가 입력으로 주어진다면
2 -> 5와 5 -> 2가
동시에 연결되는 것과 동일한 것이다.

나는 이 문제를
벡터와 큐를 이용하여 BFS로 풀었다.

 

 

 

문제 구현 단계

---

void bfs(int start) {
	queue<int> q;
	q.push(start);
	c[start] = true;

	while (!q.empty()) {
		int x = q.front();
		q.pop();
		for (int i = 0; i < v[x].size(); i++) {
			int y = v[x][i];
			if (!c[y]) {
				c[y] = true;
				q.push(y);
			}
		}
	}
}

핵심이 되는 Bfs함수 부분이다.

매개변수로 시작 변수로 받아 큐에 넣고
방문을 뜻하는 배열 c를 체크한 후
큐에서 꺼내고 넣는 작업을 반복한다.

 

연결되어 있는 노드 중, 방문하지 않은 노드라면
방문처리를 해준 후 큐에 넣어 준다.


이를 큐가 빌 때까지 반복해 준다.

 

int main() {
	int N, M;
	cin >> N >> M;
	
	for (int i = 1; i <= M ; i++) {
		int v1, v2;
		cin >> v1 >> v2;
		v[v1].push_back(v2);
		v[v2].push_back(v1);
	}
	int count = 0;
	for (int i = 1; i <= N; i++)
		if (!c[i]) {
			bfs(i);
			count++;
		}

	cout << count << endl;
	return 0;
}

main함수 부분인데, 연결요소의 개수를 파악하기 위해
방문하지 않은 정점 N개를 BFS를 실행한 후,
count를 더해주는 방식을 사용해 줬다.

 

왜냐하면 연결된 노드라면
이미 이전 BFS 작업에서
이미 방문처리가 됐을 것이기 때문이다.

 

마지막으로 전체 코드를 올리고 마무리하겠다.

#include <iostream>
#include <vector>
#include <queue>

using namespace std;

vector<int> v[1001];
bool c[1001] = { false };

void bfs(int start) {
	queue<int> q;
	q.push(start);
	c[start] = true;

	while (!q.empty()) {
		int x = q.front();
		q.pop();
		for (int i = 0; i < v[x].size(); i++) {
			int y = v[x][i];
			if (!c[y]) {
				c[y] = true;
				q.push(y);
			}
		}
	}
}
int main() {
	int N, M;
	cin >> N >> M;
	
	for (int i = 1; i <= M ; i++) {
		int v1, v2;
		cin >> v1 >> v2;
		v[v1].push_back(v2);
		v[v2].push_back(v1);
	}
	int count = 0;
	for (int i = 1; i <= N; i++)
		if (!c[i]) {
			bfs(i);
			count++;
		}

	cout << count << endl;
	return 0;
}

벡터와 c 배열의 범위가 1001인 이유는 문제조건 때문이다.

 

 

 

시행착오

---

말 그대로 BFS와 DFS의 대표적인 연습문제였기 때문에
푸는 방법만 알고 있다면 그다지 어렵지 않았다.