알고리즘(C++) / 백준 11724 : 연결 요소의 개수

11724

boj.kr/11724

11724번: 연결 요소의 개수

 

문제

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

 

입력

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

 

출력

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

 

코드

//11724 연결 요소의 개수
#include<iostream>
#include <vector>
using namespace std;
bool visited[1001] = { false, };
vector <int> vec[1001];
int N, M;
int num = 0;

void DFS(int node) {
	visited[node] = true;
	for (int i = 0; i < vec[node].size(); i++) {
		int next = vec[node][i];
		if (!visited[next])
			DFS(next);
	}

}

int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);

	cin >> N >> M;


	int a, b;
	for (int i = 0; i < M; i++) {
		cin >> a >> b;
		vec[a].push_back(b);
		vec[b].push_back(a);
	}

	for (int i = 1; i <= N; i++) {
		if (visited[i] == false) {
			num++;
			DFS(i);
		}
	}

	cout << num << "\n";


	return 0;
}

 

설명

이번 문제는 간단한 DFS 문제이다. 

첫째 줄에 정점의 개수 N과 간선의 개수 M이 주어진다. 

둘째 줄부터 간선의 양 끝점 u와 v가 주어진다. 이때 양 점을 vec에 저장하여 이어준다.

vec에는 연결되어있는 노드가 저장되어있다. 

 

DFS, 깊이 우선 탐색을 한다. 처음 노드부터 시작하여 탐색을 시작한다. 방문한 노드들은 visited배열에 ture로 표시한다.

연결된 그래프를 모두 탐색하면 연결되지 않은 노드(방문하지 않은 노드)부터 시작하여 탐색을 시작한다. 이렇게 연결된 요소의 개수를 확인할 수 있다. 

 

결과

 

고찰

이번 문제는 그래프만 구현했다면 어렵지 않은 문제였다. 

이런 DFS, BFS 문제를 많이 풀어보면서 감을 익혀야 할 것 겉다. 

 

난이도

●○○○○