BOJ 11724 연결 요소의 개수

📎Problem Link

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

11724번: 연결 요소의 개수

 

📋 문제 정리

• 방향 없는 그래프
• 첫째 줄에 정점의 개수 N과 간선의 개수 M 입력  (1 ≤ N ≤ 1,000, 0 ≤ M ≤ N×(N-1)/2)
• 둘째줄부터 M개의 줄에 간선의 양 끝점 u와 v 입력 (1 ≤ u, v ≤ N, u ≠ v) 

📌 예제 1

위의 그림에 따라 결과는 '2'가 나와야 한다.

 

📌 예제 2

 

위의 그림에 따라 결과가 '1'이 나와야 한다.

 

---

💻 Code

 

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

class Graph {
public:
	int Vertex, Edge;
	vector <int> v[1001]; // 각 노드들에 대한 연결 요소들을 저장할 벡터 객체
	queue <int> q; // BFS 탐색을 위한 queue 객체
	bool visited[1001] = { false }; // 방문을 체크할 배열
	void BFS(int start) {
		q.push(start);

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

먼저 Graph 클래스부터 보도록 하자. 변수는 위와 같이 설정했다.

BFS 함수는 시작 요소와 함께 호출되면서 시작된다. BFS 내부를 보면 while문을 볼 수 있다. 이 while문은 q에 요소가 하나라도 남아있으면 실행된다. q.push(start)가 실행되기 전에는 q가 비어있기 때문에 while문 내부로 들어가기 위해 start를 q에 push한다.

while문을 들어가면 현재 node 번호는 필요가 없기 때문에 current라는 변수에 넘겨주고 q에서 pop된다.

for문의 v[current].size()는 현재 노드에 연결된 노드 개수들을 나타낸다. 이 모든 노드들에 대한 방문 여부를 확인한 후, 방문하지 않았다면 q에 push한다.

위와 같은 로직을 반복하면 한 연결 요소의 모든 노드를 탐색할 수 있다.

 

int main() {
	int Connected_Component = 0;
	Graph ug; //undirected_graph 객체 생성
	cin >> ug.Vertex >> ug.Edge;

	for (int i = 0; i < ug.Edge; i++) {
		int u, v;
		cin >> u >> v;

		ug.v[u].push_back(v);
		ug.v[v].push_back(u);
	}

	for (int i = 1; i <= ug.Vertex; i++)
	{
		if (!ug.visited[i])
		{
			ug.visited[i] = true;
			ug.BFS(i);
			Connected_Component++;
		}
	}
	cout << Connected_Component << endl;
}

for문 내부의 if문에서 현재 노드에 대한 방문 여부를 확인한 후, BFS를 실행한다.

BFS가 실행되고 종료되면, 그 뜻은 한 연결 요소를 모두 돌아봤다는 뜻이기 때문에 연결 요소를 세는 Connected_Component++를 한다.

 

for문은 계속 돌아가며 방문하지 않은 노드에 대한 BFS를 실행하게 되고, for문이 모두 종료되면 연결 요소의 총 개수를 구할 수 있다.

---

1년 전과 비교하면 메모리는 200KB가 줄었고, 시간은 23ms가 늘었다. 아무래도 1년 전과 다르게 queue 동적 할당을 더 하다보니 시간이 늘어난 것 같다. 아무튼 11724번도 끝!