(C++) 백준 11724번 - 연결 요소의 개수

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

문제

> 방향 없는 그래프가 주어졌을 때, 연결 요소 (Connected Component)의 개수를 구하는 프로그램을 작성하시오.
> 첫째 줄에 정점의 개수 N과 간선의 개수 M이 주어진다. (1 ≤ N ≤ 1,000, 0 ≤ M ≤ N×(N-1)/2) 
둘째 줄부터 M개의 줄에 간선의 양 끝점 u와 v가 주어진다. (1 ≤ u, v ≤ N, u ≠ v) 같은 간선은 한 번만 주어진다.

접근

점과 간선을 입력받고 이를 통해 그래프를 만들어 낸 뒤 그래프 탐색 알고리즘으로 각 점에 대해 그래프를 탐색한다.
모든 점에 탐색을 하는데 한 탐색이 끝날 때 마다 수를 누적시키면 몇개의 그래프가 만들어졌고 탐색됐는지 알 수 있다.

문제해결

> 기본적인 탐색은 기존의 DFS나 BFS중 하나를 써서 하면된다. BFS를 사용하였다.
> 입력으로 점과 간선을 받고 간선 수 만큼 반복해주며 간선의 시작점과 끝점을 입력받아 벡터에 넣어 그래프의 연결관계를 만든다.
> 입력받은 연결관계를 정렬해 1번 점부터 차례대로 탐색을 한다.
> 연결관계의 수를 찾기위해 모든 점을 범위로 반복을 한다.
해당 점에 대한 방문 여부를 따지는 visited 부울형 벡터를 조건으로 해당 점을 탐색하지 않았다면 BFS함수를 호출해 탐색한다. 이는 한 연결요소를 탐색했다는 뜻이므로 cnt를 누적시킨다.
> 이제 i에 대해 visited가 true인 값은 지나가고 false인 점만 BFS의 시작값으로 넣어 다시 탐색한다.
> 예를 들어 1,2,5가 한 연결요소고 3,4,6이 두 번째 연결요소라고 치면, 처음에 1을 넣어 시작할 때 1,2,5에대한 탐색이 이루어지고 각각 true로 마킹이 된다.
그럼 for문에서 i가 1,2,5일땐 동작하지않고 3으로 넘어가 탐색이 된다. 그럼 다시 3,4,6이 마킹이 되니 1,2,5,이외 3,4,6도 동작하지않고 총 두번 동작했으므로 cnt에 2가 누적되어 출력된다.

코드

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

int N, M;
vector<vector<int>> connect;
vector<bool> visited;
void BFS(int start)
{
	queue<int> q;
	q.push(start);

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

		if (visited[k]) continue;
		visited[k] = true;
		
		for (auto a : connect[k])
		{
			if (!visited[a]) q.push(a);
		}
	}
}
int main()
{
	ios::sync_with_stdio(false);
	cin.tie(nullptr);
	cout.tie(nullptr);

	cin >> N >> M;
	connect.assign(N + 1, vector<int>());
	visited.assign(N + 1, false);
	while (M--)
	{
		int u, v;
		cin >> u >> v;
		connect[u].push_back(v);
		connect[v].push_back(u);
	}

	for (int i = 1; i <= N; i++)
		sort(connect[i].begin(), connect[i].end());
	int cnt = 0;

	for (int i = 1; i <= N; i++)
	{
		if (!visited[i])
		{
			BFS(i);
			cnt++;
		}
	}
	cout << cnt << '\n';
}

후기

구현하고 직접 동작을 따라가보면 제대로 되고 출력도 되는데 틀렸다고 나와 뭐가 문제인지 찾아봤다.
문제는 while문에서 connect벡터에 연결관계를 입력하는 부분이었다. 문제에 방향이 없는 그래프라고 하여 입력을 한번만 받으면 된다고 생각했지만 방향에 대해 공부해보니 무방향그래프 = 양방향 그래프이고 방향 그래프가 한방향이라고 한다. 즉, 입력을 양방향처럼 받아야 정답이다.