백준 : 11724번 연결 요소의 개수 Graph BFS(c++)

백준 링크

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

11724번: 연결 요소의 개수

시간 제한	메모리 제한	제출	정답	맞힌 사람	정답 비율
3 초	512 MB	106768	48227	31808	42.266%

문제

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

입력

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

출력

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

예제 입력 1

6 5
1 2
2 5
5 1
3 4
4 6

예제 출력 1

2

예제 입력 2

6 8
1 2
2 5
5 1
3 4
4 6
5 4
2 4
2 3

예제 출력 2 복사

1

코드 풀이

문제에서 주어진 간선과 정점을 Graph벡터를 생성하여 연결 후 큐를 활용하여 BFS 탐색을 진행하였다.

1. Graph 연결

int answer = 0;
int N, M;

cin >> N >> M;

vector<vector<int>> Graph(N + 1);
vector<bool> Visited(N + 1);

for (int i = 0; i < M; ++i)
{
    int ANode, BNode;
    cin >> ANode >> BNode;
    Graph[ANode].push_back(BNode);
    Graph[BNode].push_back(ANode);
}

2. 연결 요소 추출 및 총 그래프 순회

// 그래프를 전부 순회
for(int i = 1; i < Graph.size(); ++i)
{
    // i번째 그래프의 사이즈가 0이라면 연결 안된것이다.
    if (Visited[i] == true)
        continue;

    // 간선이 없다고 노드가 없는게 아니다. 햇갈림 주의
    if (Graph[i].size() == 0)
    {
        ++answer;
        continue;
    }

    // 방문노드 true
    Visited[i] = true;
    queue<int> qNode = {};
    qNode.push(i);
    ++answer;

	......

}

3. BFS 탐색 부분

while (!qNode.empty())
{
    int Cur = qNode.front();
    qNode.pop();

    for (int j = 0; j < Graph[Cur].size(); ++j)
    {
        if (Visited[Graph[Cur][j]] == true)
            continue;

        qNode.push(Graph[Cur][j]);
        Visited[Graph[Cur][j]] = true;
    }
}

주의해야 하는 부분

• 방향성 그래프가 아닌 양방향(방향 없는) 그래프이다
  
  
• 간선이 없다고해서 정점도 없는 것이 아니다
  예를 들어 정점의 개수 N이 6, 간선의 개수 M이 2이고 [3,1] [1,2]이 연결되어 있다고 하면 최종적인 정답은 1이 아닌 4가 되는 것이다. 즉, 문제의 정답은 연결 요소의 개수, [1,2,3]  [4] [5] [6] 이렇게 총 4개의 연결 요소 개수가 되는 것이다. 

코드

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

using namespace std;


int main()
{
	int answer = 0;
	int N, M;

	cin >> N >> M;

	vector<vector<int>> Graph(N + 1);
	vector<bool> Visited(N + 1);

	for (int i = 0; i < M; ++i)
	{
		int ANode, BNode;
		cin >> ANode >> BNode;
		Graph[ANode].push_back(BNode);
		Graph[BNode].push_back(ANode);
	}
	
	// 그래프를 전부 순회
	for(int i = 1; i < Graph.size(); ++i)
	{
		// i번째 그래프의 사이즈가 0이라면 연결 안된것이다.
		if (Visited[i] == true)
			continue;

		// 간선이 없다고 노드가 없는게 아니다. 햇갈림 주의
		if (Graph[i].size() == 0)
		{
			++answer;
			continue;
		}

		// 방문노드 true
		Visited[i] = true;
		queue<int> qNode = {};
		qNode.push(i);
		++answer;

		while (!qNode.empty())
		{
			int Cur = qNode.front();
			qNode.pop();

			for (int j = 0; j < Graph[Cur].size(); ++j)
			{
				if (Visited[Graph[Cur][j]] == true)
					continue;

				qNode.push(Graph[Cur][j]);
				Visited[Graph[Cur][j]] = true;
			}
		}
	}

	cout << answer;

	return 0;
}