[백준 11724] 연결 요소의 개수 C++

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

11724번: 연결 요소의 개수

 

 

이번 시간은 그래프의 기본인 연결 요소의 개수를 구하는 문제의 풀이법을 설명하겠습니다.

 

문제에서 조건은 방향이 없는 그래프라고 말하고 있습니다. 

입력으로 정점의 개수 N과 간선의 개수 M을 입력받고요, 연결된 요소가 총 몇개 있는지 구하는 문제입니다.

 

이 문제는 DFS, BFS로 어느것으로 풀어도 되지만, 저는 DFS를 이용해서 깊이 탐색하여 문제를 해결해보았습니다. 

 

예제 1의 입력값은 

6 5

1 2

2 5

5 1

3 4

4 6

입니다. 즉, 정점이 6개이고 간선이 5개입니다. 이 정보를 표를 통해 표현한다면 다음과 같이 표현할 수 있습니다.

	1번	2번	3번	4번	5번	6번
1번		O			O
2번	O				O
3번				O
4번			O			O
5번	O	O
6반				O

 

(1,2)가 들어왔다면 1에서부터 2로 연결되어있고 반대로, 2에서 1로 연결이 되어있습니다. (방향이 없는 그래프이기 때문에)

 

즉, 표시할 땐, (1,2)배열과 (2,1)배열을 동시에 연결되어있다고 표시하면 됩니다.

 

map[a][b] = true;

map[b][a] = true;

동시에 표시를 해줍니다.

 

이 작업이 끝나고 나서, DFS로 깊이 탐색하면서 하나씩 연결해가면 됩니다. 처음 시작할 때 count++을 해주고,

깊이 탐색으로 연결의 끝점까지 파면서 연결시키면 됩니다. 연결시키면서 이 점들을 지나쳤다는 Check배열에 표시하고, 지나치지 않은 check배열만 계속해서 탐색하면 됩니다.

 

예제 1은 정답이 2개입니다. 왜냐하면 이어지는 연결 요소가 2개이기 때문이죠

 

(1, 2 ,5) 싸이클이 있는 연결 요소 1개와,

(6, 4, 3) 싸이클이 없는 연결 요소 1개를 찾아 총 2개를 찾을 수 있습니다.

 

전체 코드는 다음과 같습니다.

 

#include <iostream>

using namespace std;


#define input_max 1000 + 1

bool map[input_max][input_max];
bool check[input_max];
int n, m, result;


void dfs(int num) {

	check[num] = true;


	for (int i = 1; i <= n; i++) {
		
		if (map[num][i] && !check[i]) {    //num -> i 방향으로 깊이 탐색 진행, 연결이 끈기거나 싸이클이 돌 때까지 탐색
			dfs(i);
		}
	}
}

void solution() {

	cin >> n >> m;


	for (int i = 0; i < m; i++) {
		int a, b;

		cin >> a >> b;


		map[a][b] = true;  // 양방향으로 간선만들어주기
		map[b][a] = true;  // 양방향으로 간선만들어주기

	}

	
	for (int i = 1; i <= n; i++) {

		if (!check[i]) {
			result++;    //시작 시 카운트 세주기

			dfs(i);      // DFS 탐색
		}
	}

	cout << result << '\n';




}

int main() {

	ios_base::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);


	solution();


	return 0;
}